I've never used multiple Approval Processes for the same object. I have a case now in which I would want a different process to run based on Record Type. Is it just a matter of making multiple Approval Processes with different entry criteria ?
Each step in a single approval process can have entry criteria, so you don't have to evaluate every step each time. I would build this as a single process (in fact I think you're going to have to, because like you said, only one is going to fire at a time). Then use the entry criteria for each step to conditionally determine if that step should fire, based on various criteria.
Yes, you can just create multiple approval processes with different entry criteria based on your object record type. This will ensure that different record types will go through different approval process when submitted.
You can check the link below for setting up approval process: https://help.salesforce.com/apex/HTViewHelpDoc?id=approvals_creating_approval_processes.htm#Filter