Web promotion is becoming a very competitive business and among them the SE war is the most difficult one. Directories are yeasier and possibly the most value in terms of effectiveness, time spent and resources needed to pull it off.
My advice is to go first after the directories, but not after some serious thinking and reading some guides. Second is the networking part. Networking basically refers to link sharing and other coverage. The other three options are good, but you need more resources, compared to the first two, for them to by effective. If you are new to this field you should browse though some of the material available on the subject. For example my site (http://www.webpromotionadvice.com/) has an article base on web promotion designed with a small/medium target group with a limited budget in mind. But it is not the only one and you can find a lot of good material out there (and a lot af bad too ).
I just wanted to say that your site really looks great.
First you should do the basics:
-Search engines and directories (yahoo!!!!),
-I would do goto.com,
-You don't have a "tell a friend" link (at least I didn't see one)!
-You should have a "link to us" thing.
Maybe you should run contests:
-Make a database for everybody that refers a friend, then draw a winner.
-Make it easy for people to link to you, give them some ready made html code, that will add the persons name to a database when someone clicks on the link, and then draw a winner from the list.
Use your imagination
Anyway, to promote more, you first have to think of what you want. Yes, it sounds stupid, but there are many different ways to promote.
Do you just want name recognition?
Do you want clicks?
Do you want people to sign up for something?
Think about signing up with a pay per click or signup contract, at least you are sure that you get results.
Also, a good way to advertise is newsletters. http://www.advertising.com has a newsletter program, I can't give you the exact address because their site is framed, but it is easy to find.