Inbound Marketing is something you should look into. Along with that, here are some steps you can do to build a user base:
- Define your ideal user. Get as specific as you can.
- List your competition and complementary tools for your application. The best place to find users are places that already provide the service and any complementary services. For example, an accounting service might team up with a billing service.
- Make it easy for customers to find you. This is where Inbound Marketing comes in. Basically, you want to create content that makes you visible to customers via different types of media (guest posts, blog, Twitter, Facebook, etc.).
- Demonstrate you solve problems by creating advocates for your solution and allow users to try it for free.
All situations are different but these are some of the basics. The real trick is to truely solve a customer pain and then get the word out as effectively as you can.