How do you determine what transaction fee to offer when sending from wallet?

I have read a number of posts/stories from people who have had their transactions not show up for extremely long periods of time (such as when sending to an exchange) and it turned out that they had not set any transaction fee in their wallet. So I am paranoid and always use a transaction fee.

But how can you determine what is enough to get your transaction processed in a reasonable timeframe, but not unnecessarily high? With some QT wallets it says a "suggested" fee but what is that based on? And some, like potcoin, don't list any suggested fee at all - and if you try to send potcoin in any substantial volume it starts trying to multiply whatever transaction fee you have set several times over (For example I tried setting the fee to 0.1 and when I tried to send 6200 it tried to charge me .4 wtf?)