learning roadmap - How can I learn about doing linear algebra with trace diagrams?

The best resource I can point a beginner to is the first few chapters of Stedman's book "Group Theory". He focuses on the specific example of 3-vector diagrams, and does a good job of including lots of sample calculations. Unfortunately, it's not available online. I have found Cvitanovic' book fascinating but tough to internalize. You might also try looking at some of the work of Jim Blinn (a compilation of his work is at http://research.microsoft.com/pubs/79791/UsingTensorDiagrams.pdf), which has a lot of examples worked out. Another text that I commonly referred to is "The classical and quantum 6j-symbols" (http://books.google.com/books?id=mg8ISMd5mO0C), although this is limited to a special case of the diagrams.

As for learning about the diagrams themselves, I think the only way to really get comfortable with it is to work out lots of examples. I filled endless chalkboards at the University of Maryland with the doodles... it's one of the fun parts of the subject. :)

The paper you mentioned is focused on the applications of diagrams to ideas in traditional linear algebra. I have not found any other source that focuses exclusively on this use of diagrams, although Cvitanovic' book (for example) mentions without proof that one of his equations corresponds to the Cayley-Hamilton Theorem. This is probably because many mathematicians do not see much use in reproving old results (particularly if one must learn new notation to do so). I personally feel that there is sufficient beauty and elegance (once the notation is understood) in diagrammatic proofs of these "old proofs" to make them interesting. I also think that a deeper understanding of diagrammatic techniques is a worthy goal in itself. Others have mentioned some of the existing applications.

The term "trace diagrams" originated in my thesis, so you won't find it in many published papers. I use it to mean the particular class of diagrams that are labeled by matrices. There are many other names. I first learned about them in the special case of "spin networks" (a special case), and Penrose has the strongest claim to historical priority, hence "Penrose tensor diagrams".