In order to host ArcFM'ified data over the web, do we also need to have ArcFM Desktop installed or can we do without it?
Very specifically, no, ArcFM Desktop is not required to publish a mapservice to ArcGIS Server.
Note: ArcGIS Server is where the mapservice is hosted, and ArcFM Server is an extension that any given mapservice can have that adds some ArcFM functionality.
In general, the steps to publish a mapservice can be followed directly from the esri documentation.
Pre-ArcGIS Server 10.1 Note: Even though there is a method to publish a mapservice from within ArcMap, that publishes the mapservice based on an .msd, which ArcFM Server is not compatible with. Instead, publish mapservices from an .mxd in ArcCatalog; ArcFM Server is compatible with that type of mapservice.
If the intent is to publish a mapservice based on a Stored Display, it will be necessary to save that Stored Display as an .mxd and then publish the data based on that .mxd. It would be convenient if ArcFM Desktop were on that particular machine for this step, but not required.