Are GPS systems just plug and play, or does the software also have to be compatible. e.g. Could I just replace the GPS receiver in my car to one that supports Galileo (even though I don't think any are on the market yet)?
Yep, but I'm not aware of any automobiles using them yet. And I'm also not aware of any cars that allow you to swap out the navigation hardware either. Feel free to interject if you know of any!