As mentioned in What to Look For When Buying Fish, when purchasing a new fish from an LFS, it is wise to insist that the LFS guy/gal show you what the fish is being fed and demonstrate that it is indeed eating. When you get the fish home, it may not eat for a few hours because it is in a new environment, but that should pass if the fish is offered the same food that you saw it eat at the LFS.
Whatever you decide to try to feed your fish, be sure to remove uneaten food from the tank within a few hours of it being rejected. If the fish didn't eat it within that time, leaving it to rot on the bottom of the tank isn't going to make it any more appetizing to them. Also, keep in mind that throwing a whole bunch of a particular food in the tank isn't going to convince the fickle fish that it really should try it.
Know your fish and get the food to where the fish feed. A bottom dweller, like a Diamond Watchman Goby (Valencienna puellaris) isn't going to rise to the surface of the water to investigate some flake food floating there.
Live Brine Shrimp
Whether you hatch your own or buy them at your LFS, live brine shrimp are an excellent enticement for getting fish to begin feeding. There is something about the little squiggling things that most fish can't resist. Unfortunately, the older Brine Shrimp don't really have all that much nutritional value unless they have been fortified. However, newly hatched Brine Shrimp are an excellent source of protein.
Seahorses, in particular can be difficult to get to eat. Feeding a new Seahorse live Brine Shrimp is an excellent way to get a Seahorse to start eating before weaning it off to frozen Brine Shrimp, then frozen Mysis Shrimp.
Frozen Fish Foods
Frozen fish foods (Mysis Shrimp, Brine Shrimp, Krill) are much more appetizing to most fish (even many herbivores) than are flake or even pelletized foods. The smell and texture no doubt have a lot to do with this. Make sure that the frozen foods are chopped into the appropriate bite sized pieces for your fish. After the food is chopped, rinse the food with some tank water (not back into the tank). The juices that the frozen foods are packed in can cloud your tank. Rinsing through one of your small mesh fish nets works well.
Seaweed (Nori) is a natural food for Surgeonfish. Soaking the seaweed in a food additive, such as Selcon or Zoecon will add essential marine lipids and the omega-3 fatty acids to the seaweed. This will help the picky fish get more nutrition out of each little nibble. Soak the seaweed for 10 minutes in a small amount of the additive, then hang a piece of the seaweed in a food clip in the tank.
Live Feeder Fish
While you probably wouldn't want to make a steady diet of them for your marine carnivores (it has been said that freshwater feeder fish create liver problems in marine fish over time), there is something about little swimming guppies or Rosy Reds that drives carnivores crazy. If you can find them, the brackish water Mollies are probably a better choice for longer term feeding. Don't make the mistake of just dumping a bunch of these feeders in your marine tank. The freshwater fish will not normally stay alive for very long, and the ones that aren't eaten will soon end up polluting your tank. Once your carnivores are eating the live food, you can wean them of to more convenient (and less expensive) frozen foods.
A new fish to a tank will probably feel threatened by the current occupants, and will therefore not be anxious to compete for food. Make sure that your new fish has a "house" to hide in until it feels comfortable coming out in the open. You can target feed the new arrival in his house with a turkey baster.