I haven't used the XP built in firewall but from what I have picked up on this site is that it does work reasonably well. Personally, I have just purchased & installed Norton Internet Security which includes Personal Firewall. I haven't used the Internet too much since I installed it (and I am online at work at the moment) but it is doing it's job. I have had a couple of attempts to access a port and it has blocked it. Be interesting to see what other people think
If you're running you network via a router (which you probably are), then check your router's documentation since most include some sort of firewall protection. If you have an older router, check the vendors website for a firmware update that includes the firewall since most major vendors added this option with the rise in home networking over the past few months.
Then, I believe with Internet Connection sharing, only the pc directly connected to the internet needs the firewall protection. But enabling it on both systems won't affect performance at all and is just an extra layer or protection.