At the present moment, no country recognizes bitcoin as actual "currency" so the laws for exchanging, buying, selling or trading in bitcoin are exactly as they would be for simply setting up a shop. For legal purposes, pretend bitcoins are any other object, let's say a chair...
If you set up a web site that exchanges chairs for USD and you sell enough chairs, you'll probably need a business license, it would probably be smart to incorporate your chair-selling business at some point as well. If you "mine" (assemble?) chairs then you have a cost of production and you make a profit. If the profit exceeds some amount which your state/country has established then you must pay taxes on those profits. Transactions which take place using bitcoin are essentially barter transactions: whatever laws would apply if you traded an equally-valued number of chairs for that XBox 360 apply to purchasing it with bitcoins as well.
I qualify all of this with "at the present moment" because it's all quite likely to change at some point. Bitcoin is only unregulated at the present time because lawmakers are, for the most part, unaware of its presence. Once they become aware, wheels turn slowly but eventually new legalities will inevitably spring up around the bitcoin community. If you intend for your exchange to last for more than a few years it may be worthwhile to set up shop offshore in a country like Panama, where the laws are more favorable to exchanging currency.
Edit: I must also mention that bitcoins may be recognized as a "value store" without being recognized as a currency. I am not a lawyer so this should not be taken as legal advice. If you have concerns about the legality of any service you wish to run, you should contact a lawyer - though even this is of questionably little help since at present there is not (to my knowledge) any precedent for just about anything we do with Bitcoin. As with all young technologies, expect legislation to spring up around it and expect things to change soon and often.