First off, you should create an integration only user if you haven't already done so. This allows you to control security (or open up access) for the middleware integration. Typically I set the integration user's profile settings so that its password never expires, but it is not absolutely necessary.
Second, you have two different WSDL's you can choose from in Salesforce. Either the partner WSDL or the enterprise WSDL.
The partner WSDL is loosely typed, meaning that it is allows you to dynamically specify elements and attributes to an extent. This gives you some flexibility with performing XSLT transforms, or reusing components of your integration, for instance. However, it does make mapping the objects between your middleware and SFDC a bit tricky.
The enterprise WSDL is strongly typed. The downside of the enterprise WSDL is that any time your Salesforce schema changes, whether it's objects or fields, you have to refresh and re-import the WSDL into your middleware.
More info from the Salesforce docs here: http://help.salesforce.com/apex/HTViewSolution?id=000004760&language=en_US
Third is planning out the various calls you will need to make (When to query, when to insert or upsert, delete etc). Before this step, you should have a well defined data model, including perhaps external ids for upserting data, for instance.
As part of the calls to SFDC, you'll want to start mapping out your business process in the middleware layer. By this, I mean, the flow of your integration. When you insert records, when you update, how you handle errors, the frequency of the integration (is it a nightly integration, immediate, hourly, whatever).
Fourth is to write your transformations between your middleware/database and Salesforce. Usually, but not always this is done with XSLT or some derivitive thereof.
Fifth is tesing your integration. Stepping back a little, if you haven't already, pick up SoapUI. There is a plugin for eclipse as well as a stand alone version. [http://www.soapui.org/] This plugin helps you test the SOAP callouts to Salesforce before you hook them into the integration. SoapUI has saved my tail several times, and allows you to test the various calls with different parameters, etc.
Once you are ready to test the integration, make sure you have a solid test enivronment too. This means you have a test instance of the database you're integrating with, test instance of the middleware set up, test instance of Salesforce, etc. If you don't have a solid test environment, you're chances of screwing something up in production increase exponentially.
Last, if you're still estimating this work, it will undoubtedly take longer than you anticipate, so plan ahead and do your homework.
Hope that helps. - DL