Ask HN: How do you do your usability testing?

I'm working on building a site and we're in the early stages of design. In my day job, we talk a lot about usability and user-centered design but have implemented very little. I want my project to utilize some of the methods we've talked about, particularly methods gleaned from Steve Krug's "Don't make me think" and Jakob Nielsen's well-renowned site.

My question is: How do you do usability testing? What lessons have you learned? What software and equipment do you use? Is there a key piece of literature I need before I jump into this?

My budget is very limited, as this (so far) is a boot-strapped project. Any advice is appreciated.