I've never done any actual NPC movement tests to verify, but one of the videos (maybe a Beth one, I don't remember) mentions that larger triangles are more effecient. Which makes sense - more triangles makes more work.
All the triangles need to be attached. Each triangle is not seperate, so you don't want this:
If I want to add a small triangle to the side of a large one, how do I make sure the verts I place will actually be attached to the Edge of the large triangle, and not just "placed" over it?
I could try to explain the right-clicking to make new points for the triangle, but instead, I would highly encourage you to take a look at some of the navmesh videos. What would be hard to convey in words would be very easy to see in a video. Especially the Beth video that talks about "walking the dog". I think you'll find it pretty easy after you see a video.
Edit:
Video links: http://www.creationkit.com/Video_Tutorials
I'd suggest starting with: Official Tutorials #5: http://youtu.be/raM9TBZZyQY?hd=1