How can I write a makefile to auto-detect and parallelize the build with GNU Make?

The detection part is going to be OS dependent. Here’s a fragment that will work on Linux and Mac OS X:

NPROCS:=1
OS:=$(shell uname -s)

ifeq($(OS),Linux)
  NPROCS:=$(shell grep -c ^processor /proc/cpuinfo)
endif
ifeq($(OS),Darwin) # Assume Mac OS X
  NPROCS:=$(shell system_profiler | awk '/Number Of CPUs/{print $4}{next;}')
endif

To get it working you are probably going to have to re-invoke make. Then your problem is preventing infinite recursion. You could manage that by having two makefiles (the first only resetting the -j value), but it is probably possible to finesse it.