Originally Posted by in the flesh
I am using a PC, Windows XP HE, and I'm not using any sync software
There should be some way to sync your contacts with your pc to outlook, then you'd be able to sync them in iTunes with the iPhone. Pretty easy in most cases.