There's no way of writing a plugin using an interpreted environment like Firefox's Javascript, instead you have to create a binary library in a DLL. These are known as Browser Helper Objects, and give you the ability to catch browser events like page loads, and work with the DOM, but don't offer any UI access for things like toolbars.
Since we'll need to compile a DLL, the first thing we need is a compiler. Luckily Microsoft has released a cutdown version of Visual Studio for free, though there are some limitations that I'll describe. I chose to use C++ to create the DLL, because I know it well and it's what most of the BHO examples use, but you could also use C# or Visual Basic.
After we've downloaded the compiler there's some other components we need before we can build a DLL. Since the BHO is a win32 DLL, we need the platform SDK. To get it working with the express edition of Visual Studio, we'll also need to muck about with some config files, as described in this MSDN article.
For dealing with COM code, ATL/WTL is very useful, so I'd also recommend downloading the open source WTL from MS, and following the steps in this CodeProject article. Folder permissions for editing the ATL headers in the SDK are tricky in Vista. You need to make yourself the owner, and only after that sort out the permissions. You'll also need to add the mfc include folder from the SDK too.
One common problem on Vista is that the registry setting build stage of most examples will fail. To fix this, you can run Visual C++ as administrator by right-clicking on the app and choosing that option from the menu.
You're also very likely to need advanced string handling, and regular expressions. C++ inherits C's built-in strings, as either char (for ASCII )or wchar_t (for Unicode) pointers. These are pretty old-fashioned and clunky to use, doing common operations like appending two strings involves explicit function calls, and you have to manually manage the memory allocated for them.
We should use the STL's string class, std::wstring, instead. This is the Unicode version of std::string, and supports all the same operations, including append just by doing +. The equivalent for Javascript's indexOf() is find(), which returns std::wstring::npos rather than -1 if the substring is not found. lastIndexOf() is similarly matched by find_last_of(). The substring() method is closely matched by the substr() call, but beware, the second argument is the length of the substring you want, not the index of the last character as in JS!
For regular expressions, our best bet is the Boost Regex library. You'll need to download and install boost to use it but luckily the windows installer is very painless. Once that's done, we can use the boost::wregex object to do Unicode regular expression work (the boost::regex only handles ASCII). One pain dealing with REs in C++ is that you have to use double slashes in the string literals you set them up with, so that to get the expression \?, you need a literal "\\?", since the compiler otherwise treats the slash as the start of a C character escape. The regular expressions functions themselves are a bit different than Javascript's; regex_match() only returns true if the whole string matches the RE, and regex_search() is the one to use for repeated searches.
Tomas Karlsonn kindly sent me an update to these instructions for Express 9.0. "I had to modify setup80express.js (from codeproject.com), to change all references from 8.0 to 9.0"