How do you shutdown or restart a Windows computer over a Remote Desktop connection?

Open a command window (or Windows Key + R) and type the following...

...to restart:

shutdown /r /t 0 

...to shutdown:

shutdown /s /t 0 

The answer Marcus Adams gave also has a keyboard shortcut: Ctrl+Alt+End. You do have to be in full screen and/or have the RDP session set to Apply Windows key combinations on the remote computer. This effectively sends a Ctrl+Alt+Del to the remote computer (so it's handy to know for other occasions/uses too). From there, as Marcus said, you can get to Restart, Shutdown, etc. from the little red power button icon in the lower right corner.

Alternatively, you can click once on the Desktop (or the Taskbar) of the remote computer, then press Alt+F4 and you get the old-fashioned pop-up with all the shutdown options in the drop down.

Update: as noted in the comments, Ctrl+Alt+End in Windows 10 only gives you the option to Disconnect. You can't Restart or Shutdown from there. I also can't find a Windows Security option in the Start Menu... But no worry, as mentioned the Alt+F4 method still works, and I use that exclusively now (I remote in for work every day, and also manage multiple machines at home).

From Ways to shutdown/restart your computer via Remote Desktop

Another trick is to click on the desktop and type Alt + F4. This will call up the shutdown dialog, where you get the usual shutdown options like "Shut down", "Shut down without installing updates", "Restart", "Stand by", and "Hibernate".

Start button, then Windows Security. Click the little red shutdown icon, and you'll see the "Restart" option.

You use the Windows Security option for XP and Vista also. The restart option is deliberately removed from the normal location to prevent accidents.