I was wondering how to access a Linux (Ubuntu Karmic to be exact) on the local network when it is connected through a Mac with Internet sharing (AirPort to Wired).
Internet Sharing acts as a NAT, but doesn't provide a way to specify port mappings. So you can't initiate connections from the upstream/public/Internet side of the Mac to the Linux box.
The Mac itself should be able to connect to it, and any other clients on the downstream/private side of the Mac should be able to connect.
Without knowing what you define as "to access":
If you want to get to the command line of the Linux machine from the outside world, then you'd first need to SSH into your Mac. Then, you can SSH into that Linux machine from the Mac.
Or if you want to access port-based services on the Linux machine, then you can SSH into your Mac while specifying some port forwarding (tunneling) towards the Linux machine.