C compiler with openmp support on Mavericks via Homebrew
You called the Xcode gcc which is gcc 4.2 iirc. To use your Homebrew gcc just run gcc-49 and to compile with OpenMP support append -fopenmp.
Example with g++ for C++11:
g++-4.9 -fopenmp -std=c++11 omp_code.cpp -o omp_executable
This should give you insight about gcc and show that it's just a symlink to Xcode's llvm.
ls -la /usr/bin | grep gcc
You could just change the symlink to your new gcc-49, but you should be careful, as this might break other things for you.
If gcc-49 isn't available for you, you still have to add Homebrew to PATH.
PATH=$PATH:/usr/local/bin
export PATH
To permanently add this to your PATH, add these lines to your ~/.bashrc . If you use a different shell, you need to find the right file for it (~/.zshrc for zsh i.e.)
Invoke 'brew doctor' to see if Homebrew is set up correctly.