Well the first thing to look at is the hardware, you need to get either:
A crossover cable
or
A hub and 2 bits of CAT5 cable (not crossover)
Then you will need to look at network cards, most network cards work with Linux now so you should be ok.
Then just connect it all up
(1 NIC (Network Interface Card) in each computer. crossover cable between the 2 (or CAT5 from one to the hub (or switch) then another from the hub to the other computer) like this:
Either:
Computer 1's NIC <----- crossover cable ------> Computer 2's NIC
Or:
Computer 1's NIC <--CAT5 cable --> Hub <-- CAT5 cable --> Computer 2's NIC
Ok, now for the software (OS) side of things. Linux is damn good for networking
. It does depend on what distro you go for as to where your networking settings are located. Considering you are new I would go for something like Mandrake 9.1.
I have no experience of Mandrake 9.1 but I played around with Mandrake 9.0 for a bit and it was easy to get that onto the network.
I would just have a good look in the control panel thing in Mandrake to see if you can find the internet settings in there.
Once you do find them, you will have to decide on how you want it done. Either: DHCP (Dynamic Host Control Protocol) or Static IP address (e.g. 192.168.0.1). If you have a net connection you may also have to think about that, which one will share the connect etc etc. or do you want to share the connection?
Hope this helps a bit