There's a question on Stack Overflow here that might be of use. It relates to patching binary files in an efficient way (basically storing the differences between versions rather than the entire files).
It's also worth being aware that if you install the game files into "Program Files" on Windows Vista and up then you'd also need to take into account the user not necessarily having the permission to modify the files. There's a little bit of info from the DirectX help files here on that too.
Once you have your patch generated, you'll want to probably be checking the current version of the game exe with something hosted on the web somewhere, then download and launch a separate patcher with patch content. The main game exe won't be able to patch itself while it's running. There are plenty of cheap file hosting solutions out there you can store your patch and other data on.