Just started doing a bit of trading (never done any other trading) and already I have a few criteria:

• High volume, the lower the volume the longer it takes to make a trade and the bigger the difference will be between ask/bid. Also low volume makes it difficult to make larger trades (not that that is a problem for me yet)
• Percentage or very low trade fees, I'm only trading a few bitcoins at time so any fixed fee is going to stop me trading completely. I don't see any reason not to give a share to the exchange but it needs to be a very small percentage.
• Decent amount of movement during a 24-48 hour period, right now I am doing it for fun and I don't want to have to wait days or weeks before buying or selling
• Ease of transfer of funds, there is no point doing any trading if I can't deposit or withdraw funds
• Since the volume I am trading is so small security is not really a major issue for me but I would be ultra pissed if the whole Mt Gox thing happened to any of the exchanges I use.