Looking at the official make documentation, here is a good way to do it:
OBJDIR := objdir
OBJS := $(addprefix $(OBJDIR)/,foo.o bar.o baz.o)
$(OBJDIR)/%.o : %.c
$(COMPILE.c) $(OUTPUT_OPTION) $<
all: $(OBJS)
$(OBJS): | $(OBJDIR)
$(OBJDIR):
mkdir -p $(OBJDIR)
You should see here the usage of the | pipe operator, defining an order only prerequisite.
Meaning that the $(OBJDIR) target should be existent (instead of more recent) in order to build the current target.
Note that I used mkdir -p. The -p flag was added compared to the example of the docs.
See other answers for another alternative.