Asumiendo que el mod_rewrite está correctamente instalado... .
Quítale la \ al comienzo de la regla, pues no va y añade un RewriteBase. Sería algo así:
RewriteBase /
RewriteRule categoria/(.+) index.php?cat=$1
Esto convertiría una URL como:
http://mihost/categoria/autos
en
http://mihost/index.php?cat=autos
Saludos