Hawke,
Take a look at the netfilter stuff:
http://netfilter.kernelnotes.org/
I haven't looked at very much yet and would be interested in hearing
about it.
I did get NAT working a few years ago (though it wasn't easy) using
Alexey Kuznetsov's route2 code from
ftp://ftp.inr.ac.ru/ip-routing/.
I have no idea if this stuff still works or not.
I think you're better off starting off with the netfilter stuff and
see where that leads you.
Kevin