Okay, after an hour of frustration I figured out a way to do it. This code is awful because it's the first version I got working. Basically, ignore everything about the base64 encode because it was giving me an error that only oAuth and basic authentication was supported. Turns out Microsoft's documentation was wrong and you're supposed to just use your account key as the password in the request instead of the encoded string.
require 'net/http'
accountKey = 'KEY'
url = 'https://api.datamarket.azure.com/Data.ashx/Bing/SearchWeb/v1/Web?Query=%27xbox%27&$top=50&$format=json'
uri = URI(url)
req = Net::HTTP::Get.new(uri.request_uri)
req.basic_auth '', accountKey
res = Net::HTTP.start(uri.hostname, uri.port, :use_ssl => uri.scheme == 'https'){|http|
http.request(req)
}
puts res.body