Basically to get the fossils you have to go relic castle and talk to the lady by the stairs on the first level. You will either have a choice from Tirtouga or Archen. They will be level 25 when you revive them (at the Musuem in Nacrene city). Titouga will know:
Archen will know:
Otherwise to get the fossils from generation IV you talk to a man in Twist Mountain.
Hope this helps =)