The FRED.exe should be in your main FS2 folder (C:\Games\Freespace2\ or maybe something ridiculous like C:\Program Files\Freespace2\)
However, what you need is FRED Open, since it has a bunch of new features that everyone uses and retail (Original) FRED and FS may not work on your machine anyway. They don't work properly on mine.
The latest official release of FRED and FS2 Open can be downloaded
here. Please read the directions in the thread (sorry if I come off like a dick but a lot of people don't and then have to fix their install).
If you have a semi-new PC you'll also want the MediaVPs
here. Again, make sure you put everything in the right place.
Hope this helps!