I wonder how reverse image search services like tineye.com work ...?

Most likely you want an algorithm with a good locality of the image like for example a space-filling-curve. This sfc subdivide the image into smaller tiles and order and also reduce it complexity to 1-dimension. Then you want to scan the image in this order and do a fourier transformation of each tile because a transformation into frequencies is easier to save in a database. Now you have a fingerprint of your image and can compare it with other frequencies.

database: Generaly you have set of images that are collected from web sites. For each image extract key features (SURF, SIFT, whatever) in a form of numerical vectors associated to each image. Vectors are stored in searchable database. When you give image to TinEye this image is processed and key features are extracted. Algorithm for matching features to features in database is run and close matches are found. Associated list of images to matched features vectors is extracted and presented as links to web images.