Transactions without a fee will take a long time to confirm. If you add the fee the official client recommends (when it recommends it), then there will be no problem. I think paying more than the suggested fee will NOT usually help increase the confirmation speed. Confirmations are tied to block generation; a confirmation means the miner of a block has decided to include your transaction in that block. The transaction fee is how much you pay to the miner as an incentive to include your transaction on the block mined. But since confirmations only come with blocks, and blocks have delay between then (usually around 10 minutes), you can't have confirmations coming faster than blocks being mined, no matter how much you pay to the miner.
See
https://en.bitcoin.it/wiki/Transaction_fees
