Bitcoin is legal in most countries but you should check with your accountant or with an attorney if you believe you may get in trouble for using cryptocurrencies in your region.
As far as most countries care, Bitcoin is a digital good that is traded via a P2P network. Just like apps and movies can be purchased online, so can Bitcoin. But some countries are taking a step further and outright banned the cryptocurrency on fears that it may be used to subvert the existing banking system.
Algeria, Bolivia, Ecuador, Kyrgyzstan, Bangladesh, Nepal and Cambodia have banned Bitcoin. Vietnam allows trading of Bitcoins but forbids it as a payment instrument.
Cryptocurrencies are perfectly legal everywhere else. Make sure to discuss taxation and proper accounting procedures with your attorney or accountant.
The world map illustration on this page (courtesy of Wikipedia) shows Bitcoin status by country. Most of the world is green, with some restrictions in Russia and complete prohibition highlighted in red.