Yes, you have to turn on Remote Login in Sharing preferences.
What do you need Telnet for, it's kind of a dying Protocol.
Also you need to give us info on what version of OS X you're running.
I'm looking to run a small BBS on one of my Mac machines. And telnetting is the way to reach another system "piggy-backed" onto one of the Mac machines. My Mac is running OS X 10.5.8. I know that's kind of old, but so are BBSs.
Plus, I need to know if there is any BBS software available for the Mac.