What, generally, is the best way to find and hire an engineering firm?
Word of mouth recommendation is best, IMHO. If you don't know anyone who has this experience, then I'd suggest looking for someone whose customers are like you in terms of size and in the nature of the work they're looking for (ie. design, manufacture, documentation, prototypes, manufacturing, service etc).
Should we look locally, or is a remote firm just as good?
Reasonably local is good, you want to be able to meet face to face at least occasionally. At the very least, you're likely to want an initial kick-off meeting where you can show the engineer what you've already done and explain what you're looking for as a next step. Beyond that, phone calls and email seem to work pretty well.
How should we vet the firm?
Make sure you meet the engineer who will be working on your project in person. Do they seem knowledgeable, familiar with your type of business, and able to make helpful suggestions from an early stage? Do they obviously, clearly understand what it is you're looking for?
By all means ask for references, though bear in mind that in many cases, confidentiality agreements will mean they can't give you the names of other customers. They might be able to put you in touch with their own suppliers or service providers, though, who will be able to give you an idea of what they're like to deal with, and whether their designs tend to be right 1st time or whether they go through many revisions before never hitting production.
What are reasonable fee structures? Is this primarily a per-project or per-hour affair? If per-hour, what's a decent "going rate" ballpark?
The better idea you're able to give an engineer what it is you need, the more likely you are to be able to get a firm quote. If you can provide a detailed technical specification, list of requirements, some design acceptance criteria and a list of the documentation you require - and you promise not to change your mind! - then you may be able to get a firm, fixed price quote. If you can't provide those things, expect to pay an hourly rate, because the engineer has no way to know upfront how much work is involved, particularly if you haven't worked together before.
Without a detailed spec you should still be able to get an estimate, but bear in mind that it will have to be a bit flexible. The most important thing if you want to keep control of costs is to work out as early as you can what the final spec needs to be, and then not to change your mind halfway through. It's very rare indeed that a design can be modified part way through to "just add..." something without there being a knock-on effect and a price increase.
What aren't I thinking about?
You're asking the right questions, no problem there. The main thing to invest some time and effort in, is defining the project as completely as you can: inputs, outputs, how big can the board be, where does it get its power from, how many will you be building, who will use / test / install / maintain it, what regulatory approvals does it need and so on. A good engineer will help you answer these if you need it.