I am going to explain exactly what I do to patch the code into the roms, the procedure should be similar for the tools you would use on a mac, so hopefully it will be of some use.  If you need anything cleared up, let me know.

The first thing to do is decode the Game Genie code to a useable hex format.  I use GGConv from http://home.earthlink.net/~zazer/ because it's the most convenient, but there are lots of other programs and guides to do it; most are unnecessarily complicated.

6-character codes:

Once decoded, you will have them in the format xxxx:yy
xxxx= the memory address
yy= what to change it to

NES roms have a 16 byte header (10 hex), so you'll want to add that onto the memory address.  You can do that using a calculator in hex mode.  Now load the rom into your hex editor, go to that address and change the value there to yy

Using Snobro's example:
Super Mario Bros. 1
Game Genie code = SXIOPO (inf. lives)
Decoded to hex = 11D9:AD
Add 10 hex to address = 11E9
Value at 11E9=CE -> change to AD


8-character codes:
I've only tried this with games that use mappers 1 and 4 (MMC1 & MMC3).  Dunno if it works for others...

Once decoded, the codes will be in the format xxxx?zz:yy
xxxx= the memory address
zz= compare value
yy= what to change it to

Here's where it gets a little complicated.  You only change the value at a given memory address if it is equal to the value of zz.

Snowbro's guide tells you to use a scientific calculator to find the first value based on bank sizes then search in increments of the bank size, but I just start at the decoded hex address, and search the memory 4k at a time (1000 hex).  My way might not be as accurate, but it seems to work and i don't have to worry about using logical AND commands and stuff.

A note about the 1000 hex value:  Snowbro says MMC4 uses 8K banks (2000) and MMC1 uses 16 K banks (4000).  I use 4K because then I'm probably covered no matter which type of game I'm modifying.  Tho that's probably stupid because like Snobro said, the compare value isn't foolproof, and it's possible you might find the wrong address.  Make sure you test the games first to make sure the hack worked right.

Load the rom into your hex editor and go to the memory address (xxxx) plus 10 hex (compensate for header).  Check the value there.  Is it equal to zz?  If it is, change it to yy, if not go forward 1000 hex and check that address.  Continue to check values at 4k intervals (add 1000 hex (4096 bytes) to the memory address until you find the compare value).
Hex workshop makes that very easy because once you go to the initial memory address, all you need to do is use the goto command set to "from current position" and enter 1000.  Then you can press F5 until the cursor is on the compare value.

Using Snowbro's example:

Super Mario Bros. 3
Game Genie code = SLXPLOVS (inf. lives)
decoded= 1123?DE:BD
Memory address=1123 (add 10 hex=1133)
Compare value=DE
Change to=BD

So you load SMB3 into your hex editor
Go To address 1133
the value there is D0 (not what we want)
go forward 1000 hex / 4096 dec. to address 2133
The value there is 06
address 3133=BF
keep pressing F5, F5, F5 until finally you're at 3D133
the value is DE so you change it to BD and save the file.

Now if you wanted to make an IPS file for it, you use just use one of the IPS utilities to comapre the original rom to your modified one.

So it's not so hard really.  I'm surprised nobody's bothered to make a utility for it yet.  If I wasn't so lazy I'd do it myself, but that would mean I'd have to try and remember one of the programming languages I know, and I always get the commands for them mixed up.