Now if you read over the documentation and have never tinkered with a navmesh before, it may seem a bit overwelming. Although, it's actually very easy to generate a basic navmesh for a map that doesn't have one.

First off, you should get an idea of what a navmesh looks like, and keep in mind you must turn on sv_cheats to access these commands. So enter a map that already has a navmesh, like gm_construct, and type nav_edit 1 in console. You will now see the navmesh, you can also edit it by hand but that gets a bit tricky.
Screenshot of nav_edit enabled on gm_construct[gyazo.com]

Anyway, from my own observations, it seems the navmesh is generated much more efficiently when you mark walkable points around the map. Which would make sense if you think about it.
So join a map where there is no existing navmesh, the team fortress maps work well because they're small and the generation seems to occur quickly.

Go around the map, stand in a spot that you deem walkable, and type in console nav_mark_walkable. If it was successful, you should see the console output "Walkable position marked". You should also see what looks like a purple triangle, These will appear for every walkable spot you mark.
Screenshot showing a walkable spot that was marked.[gyazo.com]

-------------------------------------------------------------------------------------------------------------------------
(I just learned the other day that it doesn't matter if you mark all walkable spots and then use nav_generate. You should add one first and generate the map, and then use nav_edit 1 to check which spots haven't been generated. You then mark that spot as walkable and then type nav_generate_incremental. Keep doing this until you get all spots generated. )
-------------------------------------------------------------------------------------------------------------------------
So just add as many walkable points that you are necessary, make sure to mark roofs to because the generation might not reach it. After adding them, you should be seeing something like this. Screenshot of a map marked with walkable spots[gyazo.com]

There you go! Time to generate! Type nav_generate in console, and you're basically all set. Depending on the map size, this can take a very long time, patience is a must. When done in singleplayer, it may seem like your game is gonna crash or seems like it will remain unresponsive, but it will eventually complete the generation. The map will be restarted when it's finished, and to confirm it was successful type nav_edit 1 in console and check it out.

Screenshot of a completed navmesh with nav_edit enabled.[gyazo.com]

If you have any questions feel free to ask!
The better the map's navmesh is, the better the cats will function.
Also, you can mark new walkable points after generating the navmesh, and then regenerate it to get a more complete navmesh, it just takes a lot of patience.