by all-in-one unit, you mean printer, fax and scanner ?
regardless, you'll need to ensure linux will support it (windows support is pretty much a given), so decide on the print method and then see what devices it will support.
I use CUPS -
http://www.cups.org/ and it supports my old Canon BJC 255SP, but I don't do anything really fancy with it.
I think the problem you are going to encounter is that the different aspects of the unit need to be supported by both printer, scanner and faxing software, and you'll need to check all three.
Good luck