For Mac OS X apps: over the intertubes, of course. In fact, there's lots of awesome things (Sparkle auto-updater framework) that make this easy.
For iOS apps: Most of the time you don't. You could write your app as a mobile web app, but that doesn't cut it for a lot of apps. If you're determined to have a legit iOS app, you're playing Apple's game.
For Android apps: You can distribute on a number of app stores, in addition to or instead of the official Android Market. You can also offer downloads that can be installed manually, although this requires users to change a setting to allow so-called "sideloading" of apps.
I really don't like how people consider App Store apps "legit" and all the rest "illegal hacker shit".
Jailbreaking is simple and performed by millions. Support issues aside, if I were selling iOS software I would offer it in the App Store as well as on Cydia.
I never said that iOS apps not on the app store were "illegal hacker shit." Not my words.
That said, yes there are alternative app stores available for iOS devices but I would hardly call them "legitimate" since Apple defines that term with respect to their devices. The sad truth is that you have to bypass Apple's restrictions, and continue to do so for each new iOS release, to benefit from an alternate app store like Cydia.
For iOS apps: Most of the time you don't. You could write your app as a mobile web app, but that doesn't cut it for a lot of apps. If you're determined to have a legit iOS app, you're playing Apple's game.
For Android apps: You can distribute on a number of app stores, in addition to or instead of the official Android Market. You can also offer downloads that can be installed manually, although this requires users to change a setting to allow so-called "sideloading" of apps.