Legality is going to depend on your state regulations. I've looked into this and here in PA, you need to have insurance, you need to get your kitchen (or brew house as the case may be) inspected and approved by the health department, you need a food handler's permit, and I believe you need a business license.
Ask around to people that sell at farmers' markets and they can probably send you in the right direction for regulations for your state and municipality. There are usually provisions somewhere for selling homemade goods.
As far as procedure, the only way you'll be able to do it with yeast is if you pasteurize, which if you're selling stuff you'll want to keep records of your verification that you attain the proper temperature (dishwasher thermometer in test bottles is the best way that I can think of). You'll need some way to prove that it has <0.5%ABV(maybe OG and FG values for a certain number of bottles).
You'll need less documentation with force carbonating, but you will also need a kegging setup and a way to fill bottles without losing much CO2. (Fill from cold keg, or fill cold carbonated water on top of syrup).