various ways...speak to the Chamber of Commerce for that area of the country is a good starter.
Online, I would try http://www.companieshouse.gov.uk/ and use their WebCheck service (clickable link on the right). Only really useful for "proper" registered companies.
Alternatively, sign up with an online-enabled credit reference agency - plenty to choose from. Not only do you get access to company info (addresses, directors details, linked companies etc) but you also then get a financial scoring. This WONT tell you if they are safe to sign up as a customer (who is a safe customer these days?!?), it just gives you an impartial indication as to whether or not they are worth considering extending credit to.