I'm a first year computer science student. We are currently programming in java and I often try decompose my program into well named methods so that my main method logic can read as close to pseudo-code as possible.
The problem I find is that often I'm ending up writing so many small private methods that I feel I might be overdoing it. Are there any good rules of thumb or stylistic considerations to take into account when deciding whether to decompose a problem even further?
The rule of thumb is the Single Responsibility Principle. Every unit of code should be responsible for exactly one thing. That applies to methods as well as classes. If you can put a simple, concise name to what each of your many private methods are for, then it's fine. If you can only describe it as "part of" a larger operation, then it probably shouldn't be a separate method.
But from your question, it sounds like you're doing it right already.