Hello SEO Newbie:
Step 1: I recommend adding your site's URL to your signature here on DaniWeb, so we can diagnose the problem you address. You will also get a free backlink that is crawlable, and will increase your link popularity!
Next: Google, Yahoo, MSN, and Ask can read and index your PHP files. Kudos for programming in PHP!
Yahoo and the 2nd/3rd tier engines usually will include your site in their index before Google, so don't worry

- it often takes time for inclusion into Google. It can take months in many cases.
Surely your site has static pages as well. Are they indexed yet?
If your site is dynamic and uses sessions, I strongly recommend you rewrite your URL's. If you are using Apache, you use "mod_rewrite". If you are using Microsoft, use "IIS rewrite". There is no shortage of quality content on this topic.
Before you even think about off site link building, make sure that your site has a solid internal linking structure. Avoid Javascript links. A good site map can be a strong page that will solidify your internal link structure.
External link building is an area of SEO/SEM that is often the most challenging. The more commercial your product/service, the more difficult it becomes.
The first rule of thumb is to offer free quality content on your site, so that other sites will naturally link to you. But this won't happen until they know you exist.
Thus you should start by submitting your site to a few directories to get traffic and and targetted IBL's.
Use PPC to drive traffic to your new site! I cannot think of a more efficient way to market a new site on the web. You can start with as little as $5. Let your target audience know you exist!
I recommend you don't overagressively build links at first, since your site is new. This may trigger red flags in the search engine algorithms. Do not go out and buy text links with high PR, or sitewides - just yet! Start small. Buy on topic text link ads that are relevant, and inexpensive. Text link ads should serve the purpose of driving traffic
and help you rank for your chosen anchor text (note that you will not rank for your anchor text for a few months at least). Make sure you use your keywords as the anchor text (the text that is hyperlinked to your page). Don't aim for the sky just yet by choosing high volume search words. Start with targeted phrases that are not very competitive. Work your way up over time.
Participate in blogs and forums, and link out to your site.
Locate targeted niche directories to submit your site to, as well as the some SEO friendly directories. I usually recommend a Yahoo directory listing for $299 / yr. DMOZ.org is free, but can take years for inclusion.
Stay away from off topic link exchanges! Only swap links with partners if the links you place on your site benefits your site's users!
Write articles with your hyperlink included. Submit your article to relevant sites. Many webmasters will jump to include your article if it is well written and on target to the site's audience.
There are many forums, web sites, ebooks, pdf's, and tutorials dedicated to link building. All the major search engine sites have lots of information relevant to this topic.
Good luck with your new site, and keep posting on DaniWeb.