You have to take a holistic approach to promoting a blog, you can't just focus on one area.
Getting an analytics or similar account so you can track your traffic is first.
Listing your blog with search engines, blog directories is second.
Set up accounts for feeds with sites like feedburner.com, etc..
Publicize through .sig files, MySpace, Facebook, forums, etc...
Write interesting content, update frequently, often linking to similar posts on high profile blogs.
Approach other bloggers about guest spots on their blog or about posting on yours.
Tag your posts. I just started using Simple Tags for Wordpress on my personal blog and I love it.