Why does $\sqrt{\frac km}$ represent angular velocity and not frequency? When I break down $\omega = \sqrt{\frac km}$ (angular velocity for a simple harmonic oscillator) into its units, I get:
$$\omega = \sqrt{\frac{kg * \frac {m}{s^2}}{kg *m}}$$
which simplifies to:
$$\omega = \frac 1s$$
If I'm not mistaken, that is the unit for frequency (hz). I know that radians are considered "unitless", but I do not understand intuitively how it translates to angular velocity ($\frac{rad}{s}$) or how radians are involved.
 A: "Angular velocity" can be used inter-changably with "angular frequency", but you want to distinguish clearly between those and "cyclic frequency" which is the thing usual just termed "frequency".
The angular quantities are measured in radians per second, while the cyclic frequency is "cycles per second" AKA hertz (Hz).

The "angle" here is not obvious the first time you see it. There are two equivalent ways to understand it at first:


*

*Just accept the math as a guide The $\omega$ appears in the argument to sines and cosines when you write down the time evolution of position, velocity, etc, so $\omega t$ represents a angle and must have angular units.

*The "reference circle" To explain SHO in a class where the students don't have calculus we consider an object in uniform circular motion and then project that motion into one-dimension.1 In this view there is an actual angular velocity around an actual circle, but we're just using it to show that SHO is equivalent to the behavior of uniform circular motion along a single axis. 
You might object that neither is very satisfying--one purely abstract and the other referring to a teaching/calculating aid and not to objective reality--and to my mind you'd be right.
A more fundamental explanation comes from considering the system in Hamiltonian phase space where its path is a circle2 and has angular frequency $\omega$.

And yes, radians are formally dimensionless so you can write angular frequency as just $\mathrm{s}^{-1}$. But you'll hate yourself in the morning.

1 I actually use an object on a rotating table and a spot-light to demonstrate this construction: the shadow of the object executes 1D SHO on the wall. I've seen a demo where that was paired with a pendulum that could be set swinging next to the wall so you can see that the swing and the slide of the shadow really do correspond, but I never got that rigged for my own classes.
2 The phase space is an abstract space (position, momentum). To get a circular path for the SHO you must use suitably scaled coordinates, but they are also the ones that make the system's energy proportional to the square of the vector in that space and related to the construct that we use to get the ladder operators for the SHO in quantum mechanics and so on. It's all very elegant, but you aren't tooled up to follow the details when people first tell you that $\sqrt{k/m}$ is the "angular velocity".
A: Angular frequency (rad/s) and frequency (1/s=Hz) have the same physical dimensionality, as OP correctly figured out, but are related by a factor of $2\pi$. 
The inverse of this quantity is time, in one case the time it takes to go one radian in angle and in the other to go the full revolution. (There are $2\pi$ radian in a full circle.)
If you are given some physical quantity like $\sqrt{k/m}$ and you are not sure which of the two is it, there is only one way to find out, and it is to solve the equations exactly and find out the period of one oscillation and then compare. In other words, the quantity $\omega$ in the formula $\cos(\omega \, t)$ is an angular frequency, and $\nu$ in $\cos(2\pi\nu \, t)$ is the ordinary frequency, and obviously $\omega=2\pi\nu$ and the period $T=1/\nu$.
A: Looking into the equation of motion of a mass attached with a spring of spring constant, we get 
$$\frac{d^2x}{dt^2}= - \left( \sqrt{\frac{k}{m}} \right)^2 x \;,$$ 
which is analogues to the equation 
$$\frac{d^2x}{dt^2}=-(\omega)^2 x \;.$$ 
(Obtained by double differentiating $x=ACos(\omega t+\phi)$). Here $\omega$ is the angular velocity not frequency. 
