What techniques can be used to make a given font more legible at smaller sizes (in the 6-9pt range, for example)? Will legibility be entirely dependent on the font used, or are there other design elements that can be tweaked to help?
Yes, increase the letter spacing. Below a cetain size you should almost always do that.
Furthermore there are typefaces specifically designed for small sizes (e.g. see the ink traps on bell centennial) and families that come with specific versions of the same font for different sizes. The latter is usually indicated with specific terms: caption, text, subhead, headline/display.
Hope this helps.