How long does it take for a cited paper to show up online? I can see a couple of papers that were cited very recently and the papers containing those citations are currently online since a week or two. How long should I expect it to take before those citations show up as citations through Google Scholar or other indexing services?
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).