Install Homebrew

First, visit Homebrew homepage and follow the installation instructions to install Homebrew.

Shortcut: install the latest XCode and then run the following command to install:

/usr/bin/ruby -e "$(curl -fsSL https://raw.githubusercontent.com/Homebrew/install/master/install)"

Then add the following line to your .bashrc or .zshrc:

export PATH="$(brew --prefix coreutils)/libexec/gnubin:/usr/local/bin:$PATH"

Install the GNU Command Line Tools

(All the brew install commands below have been put into one script on GitHub for downloads.)
First comes the most important one — GNU Coreutils:

brew install coreutils

GNU Coreutils contains the most essential UNIX commands, such as ls, cat.

Then you may probably want to install the following ones (For some of the packages, you need to run brew tap homebrew/dupes first, but only once for your system):

brew install binutils
brew install diffutils
brew install ed --with-default-names
brew install findutils --with-default-names
brew install gawk
brew install gnu-indent --with-default-names
brew install gnu-sed --with-default-names
brew install gnu-tar --with-default-names
brew install gnu-which --with-default-names
brew install gnutls
brew install grep --with-default-names
brew install gzip
brew install screen
brew install watch
brew install wdiff --with-gettext
brew install wget

The --default-names option will prevent Homebrew from prepending a g to each of the newly installed commands, thus we could use these commands as default commands over the ones shipped by OS X.