Over the course of your life on Linux (or Openoffice), you will come to a point where you will face a daunting task. You will one day find the inadvertent need to send some of you work, your hard-typed work, which you so happily created using you open-source tools, and which you so lovingly adorned with open-source fonts, over to a someone who more than contended to pay Mr. Gates hundreds of dollars every couple of years. In short, you will one day need to send an OpenOffice Writer document, laced with open-source fonts over to someone who uses Microsoft Office and has never even heard of Bitstream Charter or DejaVu Sans.

Windows users note: OpenOffice is also available as a windows download. The steps described here are identical for the windows operating system as well. "PDF export" is enabled by default in the windows package.

The easiest way to do this would be to export the document as a PDF. You will find the option under the menu File > Export to PDF. If you cant find this option under your install of OpenOffice, then you need to install the additional PDF export plug-in. Under Fedora the command is:
su -c 'yum install openoffice.org-extendedPDF'
Graphically, this package:

But the problem of the fonts still remains. By default, during the export the fonts will not be embedded into the PDF and the best possible substitutions will be made when the PDF is opened on the remote machine. To embed the fonts and ensure that the documents looks the same on all platforms you need to select the PDF/A1 option in the export dialogue.

This one (Highlighted with a Blue Box):

Note: This step is identical on Windows.

To check if the embedding has worked, you can use the pdffonts command. This script checks the PDF files and prints embedded font information. The usage for the script is:
pdffonts Filename.pdf
The script accepts parameters to limit the page range and enter passwords. Use the -? argument the see the usages.

The script in action, checking a PDF file 'report.pdf':

emb stands for 'embedded' and sub stands for substitutable.