There is really only one solid solution and is the one pioneered by Quake and used in most commercial multiplayer games, which is:
Do all cheatable stuff on the server and then account for the lag that creates on the client side. This includes collisions, damage modelling, movement, etc. In quakelike engines, the client is basically just a dummy renderer for what is happening on the server that accounts for lag and does some local simulation to make sure that things don't look choppy when you're receiving data only 10 times a second.
Here's a great article that outlines how multiplayer networking works in the Source engine, and is a pretty good model to base your own code on:
http://developer.valvesoftware.com/wiki/Source_Multiplayer_NetworkingOf course, there are other client-side cheating issues like disabling certain graphical features (like wallhacking in Coutnerstrike) or automating input (like autoaim bots), which you can't solve 100% no matter how hard you try. That's why there is still ample cheating going on in Valve's games even though, I'm sure they spent a lot of time thinking about this problem. The only way to solve this is to run some sort of clientside validation (like PunkBuster or Valve's VAC system) that will monitor the local computer and check for known hacks. But that's really a completely different problem.