Placing a gear around a steering shaft and using a stepping-motor driven worm gear, what would be a realistic resolution?
If your stepper does 200 steps per revolution and your worm gear has 100 teeth that is 20,000 positions. Perhaps you would be happy with 4096 positions.
How do they connect to a shaft?
Magnet on END of shaft. IC centered over magnet.
Can a hall-effect device be made to sense angular position without having rotation - so that when the device powers up, it knows what direction the single tire steering wheel is pointing?
Yes. That's why they are called ABSOLUTE angular encoders. They tell you absolutely which way the shaft is pointing.