sobo,
welcome to
RP.
you asked about getting the color back. i'm afraid it's a bit too far gone to just restore. there is some color data left, but i'd use that later on to proof out the colors for a colorization AFTER restoring what's been lost here....and there's a lot gone.
STAGE ONE:
your first task is to find the detail again, as best you can. the second task to reconstruct the missing detail...again, as best you can. once you have a decent image again, THEN AND ONLY THEN would i attempt to re-color the image. some, in other images like yours, have done a semi-passable job of restoring color as the restoration, but it was rather hit and miss and not what i would call a client-worthy job. it could possibly be done that way, but i think in the long run you're going spend as much time or more trying to do it that way than to just restore and then colorize.
so, finding the detail. the first step is to desaturate the image. dont go to grayscale, but do go to no color by desaturating. this can be done with things like the Fast Fix plugin, or with a hue/sat/lightness filter and simply reducing the saturation to 0. that will give a decent base image to work with.
curves, contrast/brightness, levels, lum frequencies, 32 band gray, clarify, high pass sharpen, and noise reducers are going to be your next steps. these are almost all tools that will tend to bring out detail by using contrasting methods. in other words, you're going to sharpen by contrast. you can also use blending modes with layers. you do one tool, make a duplicate and test some blend modes between those layers. this will often give you a bit more detail as well.
basically, all you want to do is find the image first. that's all. it's blended into all that discoloration and fading. you have to bring it back.
STAGE TWO:
once you get the best you can with those type methods, it's now a matter of reconstructing what's just totally lost and cant be brought back any other way. first, find what's there. second, add back what shld be there and isnt.
and this is going to be the tricky part. some folks start here and it's almost always a mistake. you're going to use tools like clone, and push, and smudge and airbrush. you're going to borrow parts of the image to reconstruct other parts. or, you're going to simply create those missing parts newly.
the best way to do this is to make a new blank raster layer. you'll do all of your work on this or on successive blank layers adding one to the other. you set your tools to 'use all layers'. and you also leave good restored layer(s) turned on so that you can 'use all layers'. but, you're going to putting all the cloning, pushing, smudging and so on, ONTO the blank layer, not your restored layers. with the blank layer on top of the restored layers, the changes will be on top and appear to be on your good layers. so, you'll see your progress as you work as if it were being done on the good layers.
you simply work with these type tools to reconstruct what shld be there. there is enough detail in your image that you're going to be able to do this fairly well. you can see his lips, for instance, even if it is somewhat cluttered up. so, you remove the clutter and bring out the lips a bit more.
this may not always be truly reconstruction. some of it is still restoring, things like the lighen/darken tool are normally restorations since they are non-destructive. clone is often thought of as restoring as well, but because it is destructive, i tend to class it more as a reconstruction tool.
you may also find that it helps to do a bit of cloning and smudging in stage one, especially if it's easy spot removal type things. that's fine. whatever works. but i'd save the major work for stage two with those tools.
once you've done all the stage one stuff and the stage two stuff and you're satisfied you have a good, clean image again, THEN move on to your re-coloring. dont try to color this image before that or you wont like it. you'll be adding complexity you dont need if you do so.
i'm attaching an image that i took through stage one and partially through stage two. i could put hours and hours in on this type of image and i just dont have the time to do everyone's. besides, i'd be spoiling your fun

i mostly concentrated on the faces. in fact, while i was working in the early stages, i made the determination of 'what's important here?'. what is the real picture here? well, obviously it's the man and the girl, but even more, it's their faces. so, when doing all the previous work, i check the faces. did this action make them better or worse?
i also concentrated more on his face than hers. hers is going to be the more difficult. being the smaller object there is less detail left. and i tend to work from easy to difficult.
also, for those who are throwing away the blue channel, i'd highly recommend not doing so. there is some detail there and you're throwing it away. a brightness/contrast adjustment layer applied to just that channel will bring back a surprising amount. you could probably also use a curves or levels on it. in fact, i found that by splitting the channels and applying a brightness/contrast adjustment layer on each channel and then combining them back made for a pretty good starting point.
craig