It depends. Are you already an expert on C#, C++, or Smalltalk? If so, looking at other code examples and diving into writing your own code might work best. Do you only know a procedural language like BASIC or COBOL? If so then a book on object-oriented programming concepts generally would be a better start before getting into Java itself (or Smalltalk or C#, etc.). Do you know OO programming, just not an expert, and want to get into Java? I recommend a book on Java over a video. Depending on your learning style, a CD with the book's code example could be nice so that you can load the code into Eclipse and play around with it rather than just staring at the code on paper. The problem with a video is that it's linear. When I study a programming language, I need to refer back to past things to make them connect with what I'm currently learning, etc.
For me, I was already an expert in C++. So when I wanted to learn C# (similar to Java), I just went on-line and read the most raw description of the language's grammar / syntax, started writing code, and used Google to get an answer whenever I became stuck on something.