This is all very possible and easy once you understand the Visualforce/Apex/Custom Object arrangements. We have a complete voyage booking application written that mainly uses custom objects, apex code and visualforce pages. 

You will need to understand the Apex object/class model. If you are a Java/C++/C#/VB.net programmer this is very easy.

You will need to define a "Site" for the public to access. Look into Setup > Develop >Sites 

You must also allow the public access to your custom object otherwise no records may be inserted. 

The default web page for this site will be your visualforce page. This visualforce page will name your new Apex class as its controller.

The controller can have one method which will save the values input to the page into your custom object. 

The important thing to remember when developing this type of code is that you will also need to develop a testing method in your apex code. At this point you will need to make use of the Page Reference object to allow the test method to invoke your controller class.

Leave time for this in your estimates. If you do not incorporate a test method in your plans, then you will be able to create all the programs in development but you will not be able to move any of them into production. All apex code must be tested before it can be moved into a production environment by invoking such a test method. The test method must not generate exceptions in your class and at least 75% of the code in the class must be tested. I personally would aim for 100% of the code unless you have other non program ways of testing your code (such as external testing routines). 

Hope this helps. If I have not then please write back with more specific questions.