"Code to interfaces" is considered good practice. Such code is easy to unit test and enables loose coupling. Users only know the interfaces and the onus of wiring concrete objects is upon the top-most level (this can be done in some init code or with the help of frameworks).
My question is about following the practice of code to interfaces: does it imply that a concrete class can never declare any public method which is not present in its interface?
Otherwise, it will force users to depend upon the concrete implementation. This will make such methods difficult for unit testing; if the test fails, determining if it failed due to an issue in the caller code or due to the concrete method will require extra effort. This will also break the Dependency Inversion Principle. It will induce type-checking and down-casting, which are considered bad practice.
That is totally acceptable provided that the new methods aren't crucial to the operating of the class, and in particular to how it functions when someone thinks of it as the superclass or interface.
ArrayList provides good examples. It has methods that let you manage its internal memory, like ensureCapacity(int) or trimToSize(). Those are sometimes helpful if you know you're working with an ArrayList and need to be more precise about memory allocation, but they're not required for the basic operation of the ArrayList, and in particular, they're not required for having it operate as a general List.
In fact, interfaces themselves can add new methods in this way. Consider NavigableSet, which extends Set. It adds a whole bunch of methods that rely on the ordering of the set's elements (give me the first, the last, a subtree starting from here, etc). None of those methods are defined on Set, and even the fact that the elements are ordered isn't defined by the Set contract; but the Set methods all work just fine without the additional methods and ordering.
The advice to "code to the interface" is a good start, but it's a bit over-generalized. A refinement of that advice would be, "code to the most general interface that you need." If you don't need ArrayLists's methods (or its contract, such as its random-access performance), code to List; but if you do need them, then by all means use them.