This turns out ato be fairly tricky because of the way Beamer is set up. You will probably need to read the large pdf documentation fairly carefully, but meantime:

The Madrid theme uses the whale color theme. So you could start by creating a new theme as a copy of Madrid, say myMadrid. Then edit myMadrid and change the reference to whale to (eg) mywhale. Copy the whale theme to mywhale.

Finally you're in a position to edit the new color theme. This is the part that's tricky; but to get, eg, a red background for frame titles and some other stuff you'd change the def of  palette primary to

\setbeamercolor*{palette primary}{use=structure,fg=white,bg=red}

at this point you can experiment with other items. Good luck!