Yes, AFAICT, it's downloaded (and cached) over your Internet connection. This is similar to Maemo Mapper's approach, But Ovi Maps uses vector data rather than bitmaps and can do on-device routing etc.

I'm not sure there would be a "this data is free" thing from the carrier - if you got it through them you're probably on a contract including some quantity of data per month.