A colored background means that the Pokémon can be found in this location in the specified game. A white background with a colored letter means that the Pokémon cannot be found here.
Note that there are more than two Trainers in the Relic Castle, it's just that the others cannot be battled until later on in the game. Also, some of the items and available Pokémon can only be found on the lower floors, which again aren't important until later on. Anyway, head north, then west. Remember to walk and not run through the quicksand patches. If you run, then you will be pulled under and will have to reenter this particular floor. However, if you walk then you won't fall through the floor. When you have gone as far west as possible, walk south and talk to the Backpacker nearby. She will give you a choice between two Fossils: the Cover Fossil and the Plume Fossil.
Tirtouga is a Water/Template:Type2, while Archen is a Rock/Template:Type2. The one you pick has no effect on future storyline elements, so choose the one you like best. Now that you have chosen the fossil you want, you can either return to Route 4 and go north to Nimbasa City, or you can head all the way back to Nacrene City to resurrect it.
Nacrene Museum
Once you arrive at Nacrene City, head straight to the museum and talk to the lady behind the desk on your right. She will go off with the fossil to resurrect it and will give you the newly-resurrected Pokémon. Make sure you have less than six Pokémon in your Party. Both Pokémon will be at Lv. 25. Now, return to Route 4.
Route 4
Now that your back on Route 4, head to where the pavement reappears and follow it along until you reach the gate. Once inside, head over to where Prof. Juniper and Cheren are standing. Juniper will talk for a bit, then give both you and Cheren 10 Ultra Balls and head back in the desert to meet Bianca. Now, Cheren will talk about how Juniper gave the three of you Pokédexes as a reason for you to go on a journey. Cheren will also go back to Route 4 in order to catch more Pokémon for the Pokédex. Now, if you leave the gate via the northern exit you will find yourself in Nimbasa City.