I finally found out that the GNU coreutils package is available on Maemo as coreutils-gnu. The tools are installed in /usr/bin/gnu and available in /usr/bin with a "g" prefix. I settled on prepending /usr/bin/gnu to $PATH rather than only redefining mkdir as gmkdir, since it doesn't limit Maemo support to only mkdir.