While head-mounted display-based virtual reality (VR) can produce compelling feelings of presence (or "being there") in its users, it also often induces motion sickness. This study compared the presence, cybersickness and perceptions of self-motion (or "vection") induced when using two common methods of virtual locomotion: steering locomotion and teleporting. In four trials, conducted over two separate days, 25 participants repeatedly explored the "Red Fall" virtual environment in the game Nature Treks VR for 16 min at a time. Although steering locomotion was found to be more sickening on average than teleporting, 9 participants reported more severe sickness while teleporting. On checking their spontaneous postural activity before entering VR, these "TELEsick" participants were found to differ from "STEERsick" participants in terms of their positional variability when attempting to stand still. While cybersickness was not altered by having the user stand or sit during gameplay, presence was enhanced by standing during virtual locomotion. Cybersickness was found to increase with time in trial for both methods of virtual locomotion. By contrast, presence only increased with time in trial during steering locomotion (it did not vary over time when teleporting). Steering locomotion was also found to generate greater presence for female, but not male, participants. While there was not a clear advantage for teleporting over steering locomotion in terms of reducing cybersickness, we did find some evidence of the benefits of steering locomotion for presence.