Getting on-deck with the carriers is not easy. The carriers will sometimes require payment which can be in the millions. So plan on raising lots of capital if you want to do it.
You can always offer your software outside of the carriers official services, but they usually have it setup so that if a user installs unapproved 3rd party software it can void the user's contract. Plus the average person doesn't really install 3rd party software on their phones yet (I hope the iPhone changes this after the SDK release).
An easy solution is to offer your service off-deck, as a WAP site or a Flash Lite site. But obviously services like Loopt are not possible because you dont have access to specific phone hardware such as the GPS unit.