Have you turned on remote login in System Preferences' Sharing pane?
In older versions of Mac OS X this starts the telnet server, and in newer versions it starts the SSH server.
This service is OFF by default (for obvious reasons).
Note that it also turns itself off automatically if it finds itself disconnected from the network, which is a major pain when you've got a portable that you connect/disconnect frequently, and you've got to keep turning sharing services on every time!!!