Kite Plans

https://en.wikipedia.org/wiki/Bermuda_rig

If you're not familiar with sailing rigs, you probably don't even notice it as anything other than, "that's what most modern sailboats look like." This is precisely because it is a extremely efficient at sailing upwind. And their fastest speeds are roughly doing perpendicular to the wind.

Boats like you see in pirate movies and such have what is called square rig. These boats will sail their fastest downwind, but struggle much more in other directions.

https://en.wikipedia.org/wiki/Square_rig

EDIT: So I just realized that the Wikipedia article does not have a great explanation on the actual physics here. I'll do my best, though this is all subject to my (mis)understanding.

Obviously, just putting a sail on a raft with no other modifications will just push your raft downwind. You have some ability to control direction with the rudder, but that's it. To sail perpendicular, you need to start leveraging other forces. The main ones are lift force from the sail shape, and drag from the centerboard. [0]

Bermuda rigging uses a triangular sail that is rigged along the axis of travel. (Compare to square rig, where the sails are perpendicular to the axis of travel.) The sail has enough slack that, as wind fills it, it curves. The sails then begins acting as a vertically-oriented wing, using the airflow over the surface to generate lift -- though, in this case, the lift pushes the sailboat sideways.

So you have the wind attempting to push your boat sideways... That is not helpful for moving forward. Enter the centerboard, which resists this push by simply increasing the surface area of the boat under the water. In order to move sideways, the water has to be moved. So you have two opposing sideways forces, and the result is a bit like pushing a wedge -- the boat moves forward.

Also of interest in the physics is speed. So a boat sailing downwind can never go faster than some fraction of the wind speed. Because if it was, the apparent wind would either be zero or a headwind. However, a boat moving perpendicular or upwind can actually move faster than wind speed, because it is utilizing more forces than just the raw wind. And, in fact, the faster a boat moves upwind, the faster the apparent wind is, moving it yet faster.

[0] https://en.wikipedia.org/wiki/Centreboard

Really small boats might get away without one. For example, a Hobie Cat (around 16 feet) is using a combination of its hull and a large rudder surface to achieve the same effects.

I have been wanting to try it again using a swivel in the line to allow the balloon to spin freely, but then use a tail/fin type of attachment to keep the rig oriented. It seems like anything would have to make it better.