That phrase has always struck me as particularly American, and western American. In many places people talk of "getting the locks changed" rather than "changing the locks". It's the difference between doing something to the locks rather than swapping them out for new ones. I guess that is a reflection of the general poor quality of locks used in the US: Buying a new lock is cheaper than getting a locksmith to rekey an existing lock. And when I was on the east coast I do remember seeing more locksmiths (at least their storefronts/trucks) than on the on the west.
I think 'changing the locks' is just the American way of saying 'getting the locks re-keyed'. If that phrasing is even uniquely American, which I'm not sure of either.
Replacing a cheap (or even average household) lock is cheaper than the minimum labor charge a locksmith will charge to show up, but you still need someone to do the labor of replacing it.
Also, if you use certain brands of lock, if you buy one new lock of the same brand it comes with a special rekeying tool that will allow you to rekey all your matching-brand locks to the key that comes with the new lock.
Getting a skilled tradesperson to your house is going to cost $100 at an absolute minimum. Then parts and such. New home depo locks will be cheaper.
There are instruction available on how to change them, but even me, and I am not afraid of DIY, called one of the many locksmiths around here in Stockholm.