For the purposes of this, I'm assuming we're talking about the "classic" GameShark/GameGenie devices, which sit between the cartridge and the hardware. I believe more modern devices follow a similar principle, but are far more advanced. James' answer to this question goes into some detail about the more "modern" approach to this problem.
What's in a ROM? Well... the game, essentially.
In a video game system, the data for the game is encoded in a number of Read-Only Memory (ROM) chips, on a circuit board, which we call the cartridge. Since these ROM chips contain the game, sometimes we use the terms "game program" and "ROM" interchangeably.
The game program/ROM essentially tells the system how the game is played. For instance, pressing A in Super Mario Brothers causes a sound to be played, Mario's sprite changes (he puts his hand up) and his sprite moves upwards for a given amount of time, and then he descends back to the ground. All of this information about how to respond to a button press is encoded in the ROM.
The mechanics of the game also include how other events are considered - such as what happens when Mario loses a life. There is a value in memory that is accessed to see how many lives Mario has, and that number is decreased by one.
Patching for Fun and Profit!
The way these devices work is, they sit between the console and the ROM. (Literally - this is why they attach to the cartridge in the way they do.) In most cases, when the console asks the ROM what to do next, the cheat device simply passes that request on to the ROM, the ROM answers, and the game plays normally.
When you enter a "cheat code" into the cheat device though, it replaces (or "patches" to use a common technical term) the instruction from the ROM with the instruction you specify. In this way, you can change the way the game plays.
For instance, if you wanted infinite lives, you'd want to patch the ROM so that when the game goes to edit the value of the "lives" area of memory, it skips over the "subtract 1" instruction. If you just wanted Mario to start with more lives, all you'd have to do is go into the area of memory where Mario's lives are initialized, and make it so that instead of setting the initial value to 3, you set it to 4, or 10, or 100 instead.
The end result is that a tiny, sometimes one or two byte change in the game's program radically changes the way the game works. Suddenly Mario never loses lives, or items are never consumed, or killing a single beast gives you 10 times the experience, or you start the game with the ultimate weapon, etc.
These devices have a limited ability to store codes, and some cheats require that you patch multiple locations in memory - the more complex the cheat, or more places it would have to touch, the more codes you'd need in order to change the program in the way you want. If you had one with a large enough code space, it would theoretically be possible to change the game completely! However, since these devices lost their memory when power was removed, you'd essentially be re-writing the ROM from scratch every time you played, which would be... tedious, to say the least.
In the simplest case, the codes themselves are typically 2 parts. The first part is the ROM address to change, and the second is the value to set. These values are binary or hexadecimal values, and are typically encoded into some "easy to read" format for humans to enter into the system easily.
More complex codes had a third part, which was a "compare" value - the code would only change the value in the ROM if the existing value of the ROM program matched. This allowed certain codes to work on multiple versions of a ROM, or on cartridges that were complex enough to require bank switching (which is another topic altogether...)
The original NES GameGenie format encodes 16 bits of address and 8 bits of replacement value in hex format, which is then scrambled and encoded into 6 letters. If a "compare" value is required as well, this is another 8 bit value that generates 2 more letters, for a total of 8. This guide, by Benzene of Digital Emutations, explains the scrambling format and how you can decode a NES GameGenie code.
I don't know precisely how the people who made the initial GameGenie devices went about determining the codes they used, but the basic idea is to find the specific part of the ROM code that you wish to change. This could be done on a debug version of the console, which allows a developer to view the instructions as they are executing. Have the game do whatever it is you want to change, and then watch what part of the ROM is requested by the console. Then change the value that is read, and voila, the cheat is created.
It could also be done by extracting the data from the ROM, and examining it to determine how it works. By reading back the ROM, you can see the instructions that are executed and in what order. After analyzing the program stored in the ROM, (a process termed "reverse engineering") it's a matter of determining which instruction is key to the game's behavior, and changing it so that you change that behavior. This process can be tedious, but it gets easier with practice, knowledge, and skill.
Either of these processes would likely be difficult to neigh impossible for the home user at the time of the first GameGenie devices, although you might be able to determine the pattern of a given cheat given an existing code. For instance, if the GameGenie shipped with a code that gave Mario 6 lives, a person could probably figure out how to change the value of "6" to "7" or some other arbitrary number. The hard work is in finding the location to patch, and not the patch itself, in these cases.
The Emulation Effect
In the emulation age, code generation is easier, but also somewhat different. Emulators aren't limited to patching ROM locations - they can examine the current value of the variables of the game in real-time. This makes all sorts of interesting things possible.
Instead of just changing the game's ROM - for instance, skipping the "subtract 1 from lives" command, the emulator can change the game's state - for instance, allowing the user to just say "I want 10 lives. Now." or "I want my inventory to contain 99 elixirs." This real-time viewing and editing of the game's state makes game hacks much, much easier and game hackers far more powerful.
Where's my Xbox 360 Game Genie?
Modern gaming devices have all sorts of copy protection programs that verify and validate the ROM, to prevent piracy and ensure a "fair" multiplayer experience, among other things. This makes creation of devices similar to the "classic" GameGenie very difficult and/or illegal in some cases.