What supplements should I take?

Lots of supplements will usually equal expensive pee. Cheap supplements can often mean bad ingredients - so they aren't always a good bang for buck.
All can be done via real food, however
This is the staple
Fish oil
A protein powder post workout (good protein, try to get one with glutamine and bcaas in it. Also be a whey isolate - I use the optimum nutrition natural gold standard, vanilla. Tastes great, reasonably priced and quality)
Than maybe
A carb added post workout too (not fructose based) - but watch out as it can add weight. But can assist in muscle recovery.

That's about it.

If you're interested in getting an extra rep or two to get really strong (like 4 reps instead of 3), creatine can help but you probably will gain a few pounds as it causes more water to be retained in muscles. Take it any time during the day, you just need it in you and available - but red meat is also a source of creatine for our bodies. However, some people are considered non-responders .... it did nothing for me so perhaps I already had enough creatine stored in me because I eat meat.
Beta-Alanine is apparently safe with no side affects - except it can make you feel tingly to begin with - that will help you with some intensity and endurance. No idea what a natural comparable is.
But all of this is probably not a good idea for beginners.
Take the fish oil. Try the protein shake post workout and see how it makes you feel. Then consider adding a carb to the post workout and if you become a competitive junkie, try some other things. But be wary of expensive pee. If you see no benefit, then don't take it.
Also, a bit of caffeine pre-workout can also help.

But at the end of the day, always remember these are supplements. Not necessities or meals.

That is a complex question, and it really depends on what you are trying to address specifically. As a general baseline, I'd recommend:
Multi-vitamin
Fish oil (2-4g/day)
CoQ10 (100mg)
Vitamin D (2000 IU, maybe some/all in your multi)

If you want more:
Alpha-lipoic acid (200-300mg/day)
Acetyl L-carnitine (500mg/day)
anti-oxidants. They have a strong synergistic effect, and more or less stop cellular aging due to oxidization. They have some other positive effects as well. Good for heavy cardio, since it creates a substantial amount of oxidative stress.

Even more:
Branched-chain Amino Acids (BCAAs), 10g before and after workout, will help spare muscle and increase loss of fat (effect is not huge, but can be significant over time)

If you lift super heavy:
Creatine, ~5g/day (or find a calculator online to figure out a more exact dose), make sure you drink tons of water

If you want to be smarter:
Piracetam, 800mg 2xday
Choline Citrate, 300mg 1-2xday (if you eat lots of raw greens, then 1x... if you eat TONS, then you shouldn't need it)
must take the two together, or you will get bad headaches/brain fog. Enhances memory, attention, verbal skills, general intelligence.

That covers everything I take. I don't really consider protein powder a supplement, it's pretty much food. You need to get enough protein though (shoot for at least 1g/lb lean body mass minimum).

Here's a great resource for what is actually beneficial vs. what is a waste a money. It actually links to the sources of info, and tells you what it is used for (for instance, vitamin D is beneficial for overall health, but not for diabetes, etc)

http://www.informationisbeautiful.net/play/snake-oil-supplements/

The effectiveness of the supplements that ARE actually useful will depend very much on the individual and his or her diet as a whole.

For example, supplementing a diet with BCAAs (for a fed training protocol) when you are already getting enough amino acids from adequate protein consumption, isn't going to help you. Same goes with adding a multivitamin to a diet that is already sufficient in those vitamins.

Now realistically speaking, I don't think there's anything wrong with taking things like whey or a multi or fish oil -- just realize that you can get just about everything you need from whole food sources thus eliminating the necessity for supplements.

They are intended to supplement areas of your diet that may be lacking, with few exceptions.

The effectiveness of the supplements that ARE actually useful will depend very much on the individual and his or her diet as a whole.

For example, supplementing a diet with BCAAs (for a fed training protocol) when you are already getting enough amino acids from adequate protein consumption, isn't going to help you. Same goes with adding a multivitamin to a diet that is already sufficient in those vitamins.

Now realistically speaking, I don't think there's anything wrong with taking things like whey or a multi or fish oil -- just realize that you can get just about everything you need from whole food sources thus eliminating the necessity for supplements.

They are intended to supplement areas of your diet that may be lacking, with few exceptions.

Agreed, but most people don't get anything close to what they need from their diet. A better diet is always preferable, and getting nutrients from whole foods is certainly better than getting them from a pill, but for some people supplementation is the only feasible option.

bananas and coffee

The effectiveness of the supplements that ARE actually useful will depend very much on the individual and his or her diet as a whole.

Exactly! He right!

@wackyfunster.
What have you noticed since taking carnitine ?
Nothing ? Increased endurance ? Fat reduction ?
Or is it just something like fish-oil and vitamin, where you feel nothing but your coat looks shinier ?

I started to try it ( 2-3 weeks ?) and can't say I've noticed a thing.
I was kind of thinking it would help with endurance.

I take it for the anti-oxidant effects. There are some random studies that show minor benefit in other areas, but I'm not convinced that they are significant. ALCAR+Alpha-lipoic acid is one of the most potent anti-oxidant combos out there though. Long-term benefits in terms of cellular aging and cancer rates have been well documented with that combo, and they are cheap as hell in bulk (I think I paid something like $30 for a ~18 month supply of bulk powder).

Thanks. Ahh - You take if for a shiny coat and bright eyes (obviously, a joke for long term benefits which there's absolutely nothing wrong with).
Yes, that stuff is cheap as chips which is one reason I tried it. ($15? for 60x500mg tabs - a bit more than you, but mine is in pill-form).
I guess this is a perfect example of the pros and cons of supplementation. We were taking the same thing for different goals. My goal seemed to not be working - so it's unlikely I will continue to take this .... once my supply runs out of course - because it doesn't have any negative effects so far either. (I also read some studies that said that nothing was proven with this supplement as it relates to my goals). However you're usage is correct for you, so you will keep taking it.
Someone just saying take it, or not take it, whatever it may be, is not good advice because the intention and goal is not always clear.
Someone who has no idea one way or the other, may be taking all this stuff with no indication whats so ever that it works, and just pee money. Especially if they are being taken for incorrect reasons - e.g. creatine for recovery? Or l-carnitine for endurance:)

It's one reason I don't take creatine anymore. I noticed that I retained water and got bigger/heavier, but it did not translate into increased performance. If anything, the extra weight slowed me down on body-weight movements and running (like 6-7 pounds). I felt like the lack of benefit out-weighed any perceived benefit - even though creatine is really inexpensive, it wasn't worth it in the long run to me.

Great read all, pity there hasn't been some more contributions in this thread.
Thanks wackyfunster for that list. I'm probably going to get some of them. Not sure if I can get Piracetam and Choline Citrate here.

I'll vouch for Fish oils also - easily my no.1 supplement - it's one supplement that I don't think I've read anywhere where someone has a negative opinion on it. I suffer from joint problems in my fingers and it has made a massive difference to me.

Also recently started taking Ginseng and am pretty sure I'm feeling more energised and alert on it. I sometimes take different multi-vitamins - never really can tell any difference in myself when i have them tbh. I'm going to try one that's got a lot of biotin and vitamin D3 as one of my MFP friends swears by both of these.

This fitness journey is a bit of a voyage of exploration for me - so I want to experiment with some more supplements. I'm particularly interested to know has anyone tried Rhodiola Rosea ("The root has a reputation for stimulating the nervous system, fighting depression, enhancing work performance, decreasing fatigue....") . Seeing as I can't get Piracetam and Choline Citrate from my usual supplier, was thinking of trying Phosphatidyl Serine instead. So if someone has experience with those supplements please let me know how you got on with them.

I take a few, and feel that they are helpful.

Glucosamine ....for my knees, which are a little creaky. I find the glucosamine helps to keep them from hurting (and I don't take a mixture, just the straight glucosamine)
Flax Seed Oil........is a good substitute for fish oil, which I don't like.
Vitamin D.........women need extra D, and I live in northern MN, where natural D in the winter is at a premium.
A multivitamin for my gender and age (over 50).
Lecithin....helps to lower triclycerides (and I believe it has worked well for me, as mine were MUCH lower in this year's physical)
Extra B vitamins.............helps to increase energy and memory, can help to relieve stress, and was recommended by my doc.

My doctor checks to see what I'm taking at every physical, so I like knowing that she approves of my regimen.