How long does it take for a citation to show up online?

Google Scholar, Web of Knowledge, Scopus and other indexing services have their own ways how the papers get into their database. For Scopus, the journal has to be registered there, and then actively send the data. It's similar for Web of Knowledge I think. Google gets the data from who-knows-where and I doubt you can control it efficiently. In general, it takes couple weeks to several months.

As dgraziotin pointed out in comments, Google Scholar indexes citations from arXiv quite quickly, in couple days. However, by many people and many institutions, arXiv papers are not considered at all regarding citations, unless they are published properly elsewhere and properly Journal-ref'ed; even then, many people don't trust that the arXiv version is correct, because nobody makes any check of this (I mean, you can put whatever Journal-ref to whatever your arXiv paper, so it's not trusted).

With Google Scholar, it depends at least in part on the deal the publisher has made with Google about how soon they are allowed to scrape. For this reason, Google Scholar citations for a year keep going up for months after that year has ended.

It took four days for a Science paper (four days from online publication, three from official publication / print.)