I'm writing this post because I get asked this questions literally hundreds of times every month. Installing PowerShell is super-easy - but not always obvious. I'll also show you how to double-check the installed version and make sure you're running with the appropriate privileges.
Windows Server 2008 R2
It's already installed, and was by default. If for some reason you can't find PowerShell on your Start menu, try running C:\Windows\System32\WindowsPowerShell\v1.0\PowerShell.exe (changing the Windows path as appropriate for your system). Yes, it's under a folder called 1.0 even though it's version 2.
On the server OS, the separate graphical ISE is not installed by default. Add it from Server Manager under Features.
Note that on 64-bit systems, you'll have two copies of PowerShell and two copies of the PowerShell ISE. The "x86" version is 32-bit, the other is 64-bit. Each shell can only load extensions for the same architecture, so don't expect to find 64-bit extensions (like modules) listed when you're in the 32-bit (x86) shell. Try to run the 64-bit version unless you explicitly need to access a 32-bit extension.
Windows XP, Windows Vista, Windows Server 2003, and Windows Server 2008
Download the appropriate version of PowerShell - it's free - and install it. Note that Vista and Server 2008 came with v1.0 as an optional install; v2.0 will overwrite it and is backward-compatible with it. That download is for the entire Management Framework Core, all of which is needed to make PowerShell v2 function correctly. It also includes supporting technologies like Windows Remote Management (WinRM).
Checking the installed version
If you're uncertain what version of PowerShell you're running, just open it and run Get-Host. The results will clearly list the version. Yes, v2.0 is in a folder named "1.0," because we're still on a 1.0-compatible engine, meaning 2.0 is backward-compatible with 1.0. Future versions will also go into the 1.0 folder until Microsoft has to finally break backward compatibility, at which time they'll likely come up with a new folder name. At least, that's the current plan.
Make Sure You're an Admin
If the PowerShell window title bar doesn't say "Administrator," then you aren't - User Account Control has snagged you. Close the shell, right-click the icon again, and select Run As Administrator. That'll make sure you're really, truly an admin inside the shell.