I was testing out a site using Google Webmaster Tools and noticed that almost all the links have been 'redirected'. I receive an HTTP 301 error / warning stating such. Is this actually a big deal or is this something that can commonly happen? Some changes were made to the site recently and I don't know whether this was happening before or not.
HTTP 301 is not an error. It is just an indication that the resources you are linking to / pointing to have moved.
Normally your client should follow the redirection.
See more information on Wikipedia.