I was finally able to get things working.
First, using mingw-get I installed mingw32-pthreads-w32
This allowed me to use the -fopenmp flag with gcc.
But when using CMake I had to include the lines:
message(STATUS "Checking OpenMP")
find_package(OpenMP)
IF(OPENMP_FOUND)
message("Found OpenMP! ^_^")
# add flags for OpenMP
set(CMAKE_C_FLAGS "${CMAKE_C_FLAGS} ${OpenMP_C_FLAGS}")
set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} ${OpenMP_CXX_FLAGS}")
set(CMAKE_SHARED_LINKER_FLAGS "${CMAKE_SHARED_LINKER_FLAGS} ${OpenMP_SHARED_LINKER_FLAGS}")
set(CMAKE_EXE_LINKER_FLAGS "${CMAKE_EXE_LINKER_FLAGS} ${OpenMP_EXE_LINKER_FLAGS}")
ELSE()
message("Missed OpenMP! x_x")
ENDIF()
as normal, but I also had to make sure I had the OpenMP_CXX_FLAGS in my target_link_libraries command
set(SOURCE_FILES
src/foo.cpp
src/bar.cpp
src/baz.cpp)
add_library(<mylib> SHARED ${SOURCE_FILES})
target_link_libraries(<mylib> ${OpenMP_CXX_FLAGS})