Does Rare Candy override evolution-preventing effects such as Fossil Aerodactyl's "Prehistoric Power"?
Yes, you can use Rare Candy when Aerodactyl's Prehistoric Power is in play.
Source: PUI Rules Team (2003-09-18), PUI Rules Team (2004-07-22)
Can I use Rare Candy on a Pokémon that was devolved on that same turn (i.e. Devolution Spray, Hyper Devolution Spray, etc.)?
No, you cannot. A Pokemon must be in play since the beginning of the turn in which you are using Rare Candy. A devolved Pokemon counts as just coming into play.
Source: PUI Rules Team (2004-06-03), PUI Rules Team (2004-06-09)
Could you Rare Candy a Pokémon and NOT play an evolution on it just to get rid of the Rare Candy?
No, you cannot discard a card for free. You must be able to attach the Stage 2 card, or you cannot use the Rare Candy.
Source: PUI Rules Team (2003-10-30), PUI Rules Team (2003-12-04)
Can I use Rare Candy on a Pokémon that has already evolved normally that turn?
No you cannot, because Rare Candy can only evolve Basic Pokémon If you evolved a Pokémon already this turn, it would not be a Basic any more.
Source: PUI Rules Team (2003-10-23)
Can you use Rare Candy to evolve a Mysterious Fossil into an Omastar or Kabutops, or use it on a Root/Claw Fossil to evolve into Cradily/Armaldo?
It can. It counts as a basic Pokémon while in play. Omastar, Kabutops, Cradily, and Armaldo are Stage 2 Pokémon; you could use Rare Candy on the Fossil trainer to skip to them.
Source: PUI Rules Team (2003-10-16)
What does "This counts as evolving that Pokémon" mean, in game terms?
It counts towards the one evolution per turn for that Pokémon (with exceptions for Trainers and Pokémon Powers that break that rule) and removes Special Conditions on that Pokémon.
Source: PUI Rules Team (2003-09-26)