Selenium has some drawbacks in regards to automated testing that limit its usefulness. Notably, it doesn't handle drag-and-drop interfaces properly, and some items in salesforce.com have ID values (some cryptic) in their URL and so can't be reliably tested without extensive discovery code in the Selenium tests.
That said, Selenium can help automate the mundane process of testing Visualforce pages and other "untestable" development. The primary concern, of course, is that any data modified during a test run will remain modified after the test completes, since it is operating in a live context as far as salesforce.com can perceive (as opposed to its native test methods, which create an automatic rollback point). This is especially problematic in certain environments where data cannot be safely deleted because of potential interactions with live data that was not created through testing.
In general, the system performing the testing should be responsible for the clean up of any data it produces upon completion. Additionally, specific to salesforce.com, code space on the server is limited, while the code space on an individual computer is relatively limitless. Furthermore, since Selenium operates in a "live mode", any Apex Code framework for creating objects will also have to occupy the "live mode" code space, in turn using up the limited code space and requiring additional unit testing to cover the framework that itself is used only for testing.
While creating objects in the REST API is exceptionally trivial (even more so than the SOAP API), it is not without its drawbacks. However, since the testing is external to the native platform, the external system must assume responsibility for any data that it creates, modifies, or deletes during the course of the test run. It would make sense to develop a set of classes designed to create and delete test data so that the production system isn't polluted with this data after the Selenium tests complete.
It may be required that you will need to create "clean up tests" in case a Selenium test fails in a way that leaves test data in the production system. You would need to do this anyways with a delegated solution (again increasing code usage without any non-testing benefit), so the apparent answer would be to keep all of the testing in Selenium.
On the other hand, delegating the creation and deletion of test data to a set of salesforce.com utility classes has a distinct benefit. Tests will initialize faster since less data has to run over the wire to get things started, and the Java code would be simplified by a fair margin. This is especially important for people like me who code primarily in salesforce.com, and use Java and other languages only as auxiliary languages to perform tasks that speed up Apex Code development.
Furthermore, since primary development happens in Apex Code, making sure that the utility classes meet the requirements of the Apex Code that it supports can be tested through automation (unit tests in salesforce.com), reducing the probability that something will go wrong without noticing it earlier on. In the majority of cases, this will leave you with two types of tests that are independent of each other: Apex Code that tests controllers and utility logic, and Selenium tests that strictly test UI changes; this allows each system of testing to handle a core area of responsibility with minimal interaction or conflict.