They were profitable from their deals to supply search technology to Yahoo, etc. If they didn't call themselves profitable in their SEC filings, it was presumably because of some accounting rule about the cost of options or something like that.
In fact, IIRC it was Google's success at doing the "Get users first and profit will come" that made it fashionable among Web 2.0 startups. The idea was pretty disreputable after hundreds of Web 1.0 startups tried it and flamed out spectacularly.