If your three year old knows his ABC's, how to count, and his colors and shapes than guess what... you already HAVE begun to homeschool him. The question is whether or not you will continue.
I say go for it!
At age 3 or 4, you won't have to notify anyone. By the time he turns 5 you might have to depending on your state. In my state we don't have to notify anyone until the child is 8, but that differs from state to state. For some the compulsory attendence age 5, for some it is 6, for some it 7... and some states don't have a compulsory attendence law at all.
For those states that do have one, you can still homeschool as long as you abide by the states laws about it.
To find out about the laws in your state, go to:
http://www.hslda.org/laws/default.asp and click on your state.
Now, as for the curriculum, there are free things for preschoolers on-line.
Here is a free curriculum that starts with letters and moves on through about second grade level reading, it is Christian based, and has some Bible stories and Bible based Rhymes and stuff:
http://www.letteroftheweek.com/index.html
I like to piece together a program from several different publishers, but for preschool I wouldn't bother buying much, there is plenty you can do with with basic art supplies and a simple outline of what you what you want him to learn.
You can find a typical preschool scope and sequence here:
http://www.worldbook.com/wb/Students?curriculum/preschool
Here are some other sites, some are Christian, and some are not, but I have found that even on the non-Christian ones, you can pick and choose, you don't have to use anyting you don't like. Also some of these sites are free, and some are just companies that sell curriculum.
http://www.starfall.com (Free learning site)
http://www.handwritingforkids.com (Free worksheets)
http://www.enchantedlearning.com (Free learning site with purchased membership)
http://www.abcteach.com (free learning site with purchased membership.)
http://www.homeschooldiscount.com (on line catalog)
http://www.sonlight.com (on line catalog)
http://www.abeka.com (on line catalog)
http://www.homeschoolstockroom.com (on line catalog)
http://www.rocksolidinc.com (on-line catalog)
http://www.christianbook.com (on line catalog with homeschooling section)
http://www.earlychildhoodlinks.com (links to lots of sites)
http://www.kn.att.com (has some learning links)
http://www.first-school.ws (free preschool stuff)
http://www.wxdude.com (Meteorology studies)
http://about.com/education (information)
http://www.freeworksheets.com (free worksheets after membership purchase)
http://teacher.scholastic.com (some free worksheets and activities)
http://www.tlsbooks.com (LOTS of free stuff-no membership required)
http://www.mathsisfun.com (free activities and games)
http://www.coolmath.com (free activities and games)
http://www.dltk-kids.com (Lots of ideas and activities)
http://www.auntlee.com (Free games and activities)
http://www.funbrain.com (Free games and activities)
http://www.brainpopjr.com (Games and activities, membership required)
http://www.iknowthat.com (Free activities, registration required, but no fee for registration)
http://kidsites.com (links to lots of sites)
http://www.eclectichomeschool.org (Online newsletter and catalog)
http://www.rainbowresource.com (Curriculum company, request their print catalog, you'll never see all they offer on the website unless you know what you are looking for)
http://www.donnayoung.org (Lots of free homeschool helps, links to some free software, educational fonts, schedules for popular curriculum, record keeping forms, etc.)
http://alphaphonics.com (On-line catalog)
http://www.triviumpursuit.com (mostly ideas and articles, with some resources)
http://themathworksheetsite.com (Math worksheets, membership fee required)
http://startwrite.com (Handwriting program for sale)
http://www.letteroftheweek.com/index.html (Free curriculum for preschool to age 8)