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".

to Greg Kuperberg: Use of such diagrams probably starts in mid 19th century (Sect. 4.9 A BRIEF HISTORY OF BIRDTRACKS). If you find "spiders" or “birdtracks” too silly, I vote for the somewhat unwinged "tensor diagrams."

So why give these diagrams a new name, and not call them “Feynman diagrams” or "tensor diagrams"? I needed a distinct name to distinguish them from the more traditional uses of diagrams. The difference is that here diagrams are not a mnemonic device, an aid in writing down a Feynman integral that is to be evaluated by other techniques. I did not call them "tensor diagrams" as that is too close to “invariant tensor operators”, the Wigner-Eckart theorem, and the 3n-j diagrams that are only a prelude to a computation. Here “birdtracks” are everything, all calculations are carried out in terms of birdtracks, from start to finish.

As it happens, I used trace diagrams in my old papers on 3-manifold invariants from Hopf algebras, arXiv:math/9201301 and arXiv:q-alg/9712047. At the time I hadn't heard of the name "trace diagrams" and I called it instead "arrow notation", and I included a review of the notation. The diagrams are very useful for understanding word relations in Hopf algebras.