It's not uncommon to have a web part in the master page. First you need to add a web part zone. SPD has ribbon buttons for that. Then you can insert the web part into the web part zone.
I'm not in front of SharePoint right now. I'll post a screenshot shortly.