The worst way is to send to Recycle Bin: you still need to delete them. Next worst is shift+delete with Windows Explorer: it wastes loads of time checking the contents before starting deleting anything.
Next best is to use rmdir /s/q foldername from the command line. del /f/s/q foldername is good too, but it leaves behind the directory structure.
The best I've found is a two line batch file with a first pass to delete files and outputs to nul to avoid the overhead of writing to screen for every singe file. A second pass then cleans up the remaining directory structure:
del /f/s/q foldername > nul
rmdir /s/q foldername
This is nearly three times faster than a single rmdir, based on time tests with a Windows XP encrypted disk, deleting ~30GB/1,000,000 files/15,000 folders: rmdir takes ~2.5 hours, del+rmdir takes ~53 minutes. More info at Super User.