The Game Genie is designed to replace Cartridge ROM bytes with user entered values. It doesn't actually modify the information in the Cartridges themselves. GameBoy Games just ACT like the ROM has been modified.

This is the format for Game Genie codes for GameBoy:
 

DD

2-103

-ACB
Replace Value Address Compare Value
Late model Game Genies only require you to enter the first six digits. All nine digits are required for selecting a specific rom bank.

The DD above is the Replace Value. AB above is the old byte value in ROM to be replaced. Since there are different ways of selecting rom banks, the only way for the Game Genie to determine which byte to replace in which ROM bank is by comparing what's in ROM to the Compare Value. If these match up, then the replace value is put on the data bus. Otherwise the old ROM data is presented to the GameBoy.

The AB compare value is encoded. To restore it's original value invert AB (xor $ff), rotate value right by 2, then invert bits 0, 2 and 6 (xor $45).

The C value above is still undetermined but if you XOR it with encoded nibble A the result must not be any of the values 1 through 7 or else you will receive a bad code message. Usually this value will be 8 when decoded.

The Game Genie can only modify/replace ROM addresses 0002 to 7FFF. The most significant nibble in the address (3 above) is complemented. (i.e. it is entered as a complemented value.) ( Values:0,1,2,3,4,5,6,7 --> Complement equivalent:F,E,D,C,B,A,9,8) Values of 0 - 7 are not allowed for the most significant nibble as these are above memory locations 7FFF.

From my testing I've concluded that six digit codes affect every ROM bank. (i.e. a code that affects address 7000 will also affect virtual addresses 0F000, 17000, 1F000, 27000, etc.). This probably is not a problem for most games since graphics are usually put in these extra banks & minor 'flaws' introduced into these banks would probably hardly be noticeable. This WOULD heavily affect Multi-game cartridges though that may have code in every bank.
 
Examples Codes: Game Game Effect Technical Effect
0A1-B9F Addams Family Start with 10 lives. Address 01B9 replace with new value 0A. 
068-5FF-E66 Adventure Island  Start with 7 lives. Address 085F replace 03 with new value 06.
05D-49C-E62  Super Mario Land Start with 6 lives. Address 3D49 replace 02 with new value 05.