FIPS is a series of standards followed by the U.S. government regarding information security. There are policies, practices etc. In order to qualify to be compliant you have to make sure that you only use certain algorithms, the hardware and software you use must be deemed compliant etc.
Is it as simple as using FIPS 140
compliant crypto providers or is there
more to it?
It depends on each specific scenario, but yes it can be. For example, if certain routers you use are 140-2 compliant then your application behind them can get exemption of going through parts of the process, because the hardware you use accomplishes the same task the certification requires. For example, we use the F5 Big IP to handle a lot of our SSL etc., because they have gone through the certification process. Our other systems may be able to do the same thing, but it means we don't have to go through the approval process, which is long and painful.
http://en.wikipedia.org/wiki/FIPS_140
I think these are the links which talk about accreditation:
http://csrc.nist.gov/groups/STM/index.html
http://csrc.nist.gov/groups/STM/cmvp/index.html