Is it possible for XP to be setup to allow a Linux computer to telnet into it?
If you are using XP Professional, a telnet server is included and all you need to do is start the service (manage services by running the command
services.msc or go through the Start menu to find it) and punch a hole in the firewall (port 23). Obviously, if untrusted people can get at the port, you are running a rather large risk.
For XP Home, you will have to get hold of a server. The first one that Google foound for me is both a telnet and ssh server.
Cygwin is great for SSH access. Can't say I've tried using telnet with it though. Try these two guides for setting it up.
Yes, it is. I believe it's possible with Cygwin, which I have no experience with and cannot guide you any further than the name. Beyond that, you can install the Subsystem for Unix Applications (SUA) onto your Windows machine, which is something I have had experience with. I've been told that Cygwin is a much lighter solution, and I'm very willing to believe that because SUA is very heavy-handed. If you get the full developer package, you're basically installing all the default directories that comply to the POSIX standard and all the things you'd find in there. There'd be a folder on your hard drive that looks like the base folder of a Unix installation.
I personally ran it for some time, before I realised that in my case, it was easier to build a FreeBSD box and do what I needed to in an actual *nix environment. Because I don't know what you're planning on using this for, you'll have to choose between Cygwin and SUA yourself :)
EDIT: For some reason, I read your question as "ssh" and not "telnet." Windows XP comes with a Telnet Client, and while Vista and 7 both come with the ability to activate both telnet clients and servers, I'm not too sure about XP.
However, it seems there are a few Telnet/SSH server applications out there for Windows. Again, Cygwin and SUA would do it, but there's a boatload of others out there that would probably do what you want, like KpyM and BFTelnet. You might even find that enabling the Telnet port, 23, in your Windows firewall allows one to telnet to the computer. I'm just not certain. If it doesn't, all in all, I'd probably say go with Cygwin. If security isn't an issue, then you probably don't need anything as heavy handed as SUA.
EDIT 2: I don't have the ability to add comments yet, otherwise I would add it to
jweede's answer. http://ras52-tech.blogspot.com/2007/01/telnet-on-cygwin.html is a nice introduction to getting telnet working on Cygwin, if you absolutely need telnet and can't use SSH.