Hi --
It sounds like you have step 1 complete -- your InfoPath form has a submit connection to your desired library?
For step 2, a dropdown would be fine. Think about how often those email addresses might change, and you may want to use a secondary data connection to populate your dropdown, so that you don't have to modify the form to update the email addresses. You may want to use a SharePoint list for this information. If the only thing you need the dept info for is the email, you could have the name for the dropdown be the dept name and the value be the email. You could add an additional submit connection to your form that sends and email, and use the value of the field bound to the dropdown for the To address....
For step 3, you probably want a Manager section in your form. You may need to create user roles for hiding or displaying this information. Basing the user role off an Active Directory group is nice, because then if the managers change (I'm guessing that the Manager role is also the department head from step 2?) you can just update the group in AD instead of having to modify the form (are you sensing a theme, here?). Managers should also be able to reject the form, which would send it back to the originator. Give them a comment field, too, so they can explain why they are rejecting it. You should probably have a field in your form to store the status, so you can base logic off it.
For step 4, if you have a status field, and the Manager has clicked the Approve button (which sets status to "Manager Approved" or some such) then you can have another email submit that goes to HR (again, this address may best be stored in a secondary data source so you can look it up when it changes....). HR should be able to approve or reject. You'd need another Submit connection to the HR Archive SharePoint Library, where the form is submitted when HR sets the status to "HR Approved". Oh, and I think you'd need another user role for HR, so to only show the HR section to the appropriate user.
Hope that helps!