Generally, you should prefer interfaces to concrete classes. Along those lines, if you can avoid using the new operator (which always requires a concrete type as in your new ArrayList example), even better.
This all has to do with managing dependencies in your code. It's best to depend only on highly abstract things (like interfaces) because they also tend to be very stable (see http://objectmentor.com/resources/articles/stability.pdf). Because they have no code, they only must be changed when the API changes...in other words, when you want that interface to present a different behavior to the world, i.e., a design change.
Classes, on the other hand, change all the time. Code that depends upon a class doesn't care how it does what it does, as long as the inputs and the outputs of the API don't change, callers shouldn't care.
You should strive to nail down the behavior of your classes according to the Open-Closed Principle (see http://objectmentor.com/resources/articles/ocp.pdf), that way existing interfaces need not change even when you add functionality, you can just specify a new subinterface.
The old way of avoiding the new operator was by using the Abstract Factory pattern, but that comes with its own set of problems. Better is to use a tool like Guice that does dependency injection, and prefer constructor injection. Make sure you understand the Dependency Inversion Principle (see http://objectmentor.com/resources/articles/dip.pdf) before you start using dependency injection. I've seen a lot of people inject inappropriate dependencies and then later complain that the tool isn't helping them...it won't make you a great programmer, you still have to use it appropriately.
Example: you are writing a program that helps students learn physics. In this program, students can put a ball in various physical scenarios and watch how it behaves: shoot it out of a cannon off a cliff, put it underwater, in deep space, etc. Question: you want to include something about the heaviness of the ball in the Ball API...should you include a getMass() method or a getWeight() method?
Weight depends upon the environment the ball happens to be in. It might be convenient for callers to be able to call one method and get the weight of the ball wherever it happens to be, but how do you write this method? Each ball instance must constantly keep track of where it is and what the current gravitational constant is. So you should prefer getMass(), because mass is an intrinsic property of the ball and doesn't depend on its environment.
Wait, what if you just use getWeight(Environment) instead? This way, the ball instance can just get its current g out of the environment and proceed...better yet, you can use Guice to inject the Environment in the Ball's constructor! This is the type of misuse I often see, and people end up blaming Guice for not being able to handle dependency injection as seamlessly as they would've hoped.
The problem is not Guice here, it's the Ball API design. Weight is not an intrinsic property of the ball, so it's not a property that should be accessible from the ball. Instead, Ball should implement the MassiveObject interface with a getMass() method, and Environment should have a method called getWeightOf(MassiveObject). Intrinsic to the Environment is its own gravitational constant, so this is much better. And Environment only depends upon a simple interface now, MassiveObject...but it's job is to contain objects, so this is as it should be.