I'm just now learning TDD. It's my understanding that private methods are untestable and shouldn't be worried about because the public API will provide enough information for verifying an object's integrity.

I've understood OOP for a while. It's my understanding that private methods make objects more encapsulated, thus more resistant to change and errors. Thus, they should be used by default and only those methods that matter to clients should be made public.

Well, it's possible for me to make an object that has only private methods and interacts with other objects by listening to their events. This would be very encapsulated, but completely untestable.

Also, it's considered bad practice to add methods for the sake of testing.

Does this mean TDD is at odds with encapsulation? What is the appropriate balance? I'm inclined to make most or all of my methods public now...  

Prefer testing to the interface over testing on the implementation.

It's my understanding that private methods are untestable

This depends on your development environment, see below.

[private methods] shouldn't be worried about because the public API will provide enough information for verifying an object's integrity.

That's right, TDD focuses on testing the interface.
Private methods are an implementation detail that could change during any re-factor cycle. It should be possible to re-factor without changing the interface or the black-box behaviour. In fact, that is part of the benefit of TDD, the ease with which you can generate the confidence that changes internal to a class will not affect users of that class.

Well, it's possible for me to make an object that has only private methods and interacts with other objects by listening to their events. This would be very encapsulated, but completely untestable.

Even if the class has no public methods, it's event handlers are it's public interface, and it its against that public interface that you can test.
Since the events are the interface then it is the events that you will need to generate to test that object.
Look into using mock objects as the glue for your test system. It should be possible to create a simple mock object that generates an event and picks up the resultant change of state (possible by another receiver mock object).

Also, it's considered bad practice to add methods for the sake of testing.

Absolutely, you should be very wary of exposing internal state.

Does this mean TDD is at odds with encapsulation? What is the appropriate balance?

Absolutely not.
TDD shouldn't change the implementation of your classes other than to perhaps simplify them (by applying YAGNI from an earlier point).
Best practice with TDD is identical to best practice without TDD, you just find out why sooner, because you are using the interface as you are developing it.

I'm inclined to make most or all of my methods public now...

This would be rather throwing the baby out with the bath water.
You shouldn't need to make all methods public so that you can develop in a TDD way. See my notes below to see if your private methods really are untestable.
A more detailed look at testing private methods
If you absolutely must unit test some private behaviour of a class, depending on the language/environment, you may have three options:

Put the tests in the class you want to test.
Put the tests in another class/source file & expose the private methods you want to test as public methods.
Use a testing environment that allows you to keep test and production code separate, yet still allow testing code access to private methods of the production code.

Obviously the 3rd option is by far the best.
1) Put the tests in the class you want to test (not ideal)
Storing test cases in the same class/source file as the production code under test is the simplest option. But without a lot of pre-processor directives or annotations you will end up with your test code bloating your production code unnecessarily, and depending on how you have structured your code, you may end up accidentally exposing internal implementation to users of that code.
2) Expose the private methods you want to test as public or protected methods (really not a good idea)
As suggested this is very poor practice, destroys encapsulation and will expose internal implementation to users of the code.
3) Use a better testing environment (best option, if it is available)
In the Eclipse world, 3. can be achieved by using fragments. In the C# world, we might use partial classes. Other languages/environments often have similar functionality, you just need to find it.
Blindly assuming 1. or 2. are the only options would be likely to result in production software bloated with test code or nasty class interfaces that wash their dirty linen in public. *8')

All in all - it is much better not to test against private implementation though.

