I am using the freshnews wordpress theme that can be seen here: http://www.woothemes.com/demo/?t=6

I want to add the grey bar at the top, but i'm not sure the best way of going about it? Is it a frame, or just a CSS overlay?

On their site, that gray bar is done with frames.

Is there another way to do this without frames? Perhaps some kind of float?

I prefer not to use frames because it can sometimes hurt google's indexing.

What do you want to use the bar for?
There are a couple of plugins for WP that adds a toolbar on the top of your blog.
They're for administrative options, but you might be able to modify them.

http://wordpress.org/extend/plugins/...ess-admin-bar/
http://wordpress.org/extend/plugins/ws-tools-bar/

I want to use it as a navigation for my actual website.

Basically I have website.com and then website.com/blog

I can't modify the template enough to match my sites nav, so I want to have the overlay at the top for the public to navigate easier between the 2.