Yeah, the tutorial is pretty weak on these issues.
I suppose you can shoehorn "deadlock" into the definition of "starvation" (a thread is never allocated any CPU time), but starvation is usually a practical concern only when you attempt to manipulate your threads' priorities. Deadlock occurs due to a deterministic programming error - mismanagement of synchronization.
Starvation may depend in part on factors outside the programmer's control. The same program may exhibit starvation on one platform, yet allow all threads to run on another. Primitive JVM implementations may favor higher priority threads to such a degree that lower-pri threads never run. For most platforms and JVMs, this is a lesser concern than it used to be.
To take the simple approach, there are two things
you should do to avoid starvation. One - leave your threads' priorities alone. Two (this one's harder) - make sure that lots of threads don't gang up on a single monitor, because it's statistically possible for a given thread to never get the lock, especially if the monitor is notified infrequently. (This last one is helpful for deadlock avoidance too, BTW.)
If you must manipulate priorities and cannot guarantee that high-pri threads will finish execution quickly (or at least give up the processor in some other way than yielding), then you need to implement a thread management scheme of a higher order than simple locking, that is, you've got to build your own execution-control mechanism which guarantees a more advanced notion of "fairness" than Java's rather simple synchronization model.
Lea (Concurrent Programming in Java) mentions starvation and the more general problem of scheduling fairness, and provides an in-depth analysis of semaphores and other execution control constructs. Seems like every time someone asks an advanced threads question, I reach for this book. If you've got the basics down, you really don't need any other Java threads book. I've been told that Holub's book (Taming Java Threads) has some good utility classes, but I haven't checked it out yet.
I've yet to run into a situation where starvation was a problem. Consider that the AWT event thread and the GC run at different priorities, yet memory-intensive Java programs still do OK. The classic case for priority manipulation is a high-pri GUI to ensure responsiveness with lower-pri workers dispatched to handle user-initiated tasks, but if you're using Swing you've pretty much got to do all your UI work in the AWT event thread anyway and you shouldn't go messing around with that one's priority (I'm not even sure how to do that). Do you have a situation in which starvation is a real issue? If so, I'd be interested to hear it - an example might provide some good thought food for my late night JR lurking.
Yes, I'm still here. (evil laughter...)
jply