<p>I have a factory that returns an interface <code>FormatService</code>:  </p>

<pre><code>public class FormatServiceFactory {
    public FormatService getService() {
        ...
    }
}
</code></pre>

<p>Is it possible to mock out this factory so that it will always return a stub implementation of <code>FormatService</code> - <code>FormatServiceStub</code> in our unit tests?  </p>

Depends.  How is the factory obtained/used by the code under test?
If it's instantiated explicitly in the methods you're testing, or if it's a static factory, you won't be able to mock it.
If it's injected into the object under test, you can create and inject the mocked factory before executing the test.
Mocking the factory should be easy enough with JMock.  From your example code, it looks like it's a class, not an interface, so you'll either need to use the cglib version of JMock and the
MockObjectTestCase
class in the cglib package for JMock 1, or the
ClassImposteriser
for JMock 2.
Once mocked, you can make it return your stubbed implementation (or even a mock FormatService) when you define the expectations for the getService() method.