First, you can't have the H1 directly inside UL. Lists and tables are kind of multi layered wrappers. Nothing can be between the tags they are made up with. Everything must go inside LI in your case and inside TD and TH in the case of tables.
Start with moving the H1 outside the list. Then wrap the whole thing in a DIV. I'll explain the other changes below.
HTML
<div id="head">
<h1>The Random Website</h1>
<ul>
<li><a class="active" href="#home">Home</a></li>
<li><a href="#news">News</a></li>
<li><a href="#contact">Contact</a></li>
<li><a href="#about">About</a></li>
</ul>
<div class="clearit"></div>
</div>
The LINK should look like this.
CODE
<link rel="stylesheet" type="text/css" href="...">
^^^^
You had written text="text/css".
Now move the background color to the new DIV, which I gave the ID 'head'. Float the H1 left and set its margins to 0. I also removed the padding you had there because I don't think you want it, but I could wrong about that.
Removed the overflow: hidden on UL. See no reason for it and it can make things disappear.
Lastly, to prevent an element containing floats from collapsing we need to "clear" the floats. Floats take up no space and if there is nothing but floats in a containing element it will have no height and thus for example a background color won't show and borders will collapse to a single line. There are maybe more elegant ways of doing this that you can read about here
http://css-discuss.incutio.com/wiki/Clearing_Space , but I stick with the old style clearing DIV. That is, add a DIV last thing before the closing tag for #head and add a style rule that clears both left and right. You can try one of the other options if you like.
Think that was all. Here is the changed style sheet.
CODE
ul { list-style-type: none;
margin: 0;
padding: 0 }
li { float: right }
li a { display: block;
color: white;
text-align: center;
padding: 14px 16px;
text-decoration: none }
li a:hover { background-color: #111 }
#head { background-color: #333 }
#head h1 { margin: 0;
float: left }
.clearit { clear: both}