I know that if you want an aqueous solution with a high density, you
can dissolve salts in it. If you want a really high desity solution,
you need a salt (or other solute) that has very high solubitlity in
water. For example, you can dissolve so much potassium iodide in water
that you can produce a solution with specific gravity of 1.6 or so.
What I want to do is the same thing, except with hexane instead of
water. Is there something I can dissolve in the hexane that will
increase it's density significantly?  The solution would need to have
a specific gravity of at least 1.2, but ideally closer to 1.6.  I DO
NOT want to use halogenated hydrocarbons (chloroform etc.) and of
course, I only want to pay for idea that could reasonably be
accomplished in a well-stocked laboratory.  (No answers involving
space travel, particle accelerators, uranium, ect. allowed).

Why not use the same concept which works for aqueous solutions?
A quick look at Aldrich catalog showed CH2I2, 1,3-C3H6I2, 1,2-C6H4I2
all had densities exceeding 2.5 g/ml.  Diiodomethane has a density of
3.33g/ml, and, I am guessing here, can be mixed well enough with
hexanes to produce a solution of 1.6 g/ml density.  It is expensive @
$16 for 25g or $128 for 500g.  CI4 must be even heavier.

Now, these are all halogenated hydrocarbons, and I can't see how you
can avoid using them, since idide salts will probably not have enough
solubility to provide required density (you can try tetralkyl ammonium
salts).
Heavy metals would be much worse than polyiodinealkanes because hexane
soluble heavy metals will probably me extremely toxic.

Maybe another compound along the lines of osmocene or osmium carbonyl
might do the trick, but it would be extremely expensive.

You might be able to dissolve enough of a crown ether or calixarene
complex of Cs in hexane to bump the density up to the range you want. 
Both crown ethers and calixarenes are soluble in non-polar solvents
such as hexane, and both can be designed to form strong guest-host
complexes with metal ions. (See, for instance,
http://www.tntech.edu/chemistry/Inorganic/Chem4110/Student/13%20Calixarene-Crown%20ether%20Compounds.ppt)

I mention Cs in particular because there has been a lot of work on Cs
complexation by these classes of ligands in connection with the
treatment of high-level nuclear waste, so the chemistry is well known.

I haven't worked w/ crown ethers, but my gut tells me that in the best
case scenario, one can't prepare more than 0.01 - 0.1M solutions of
salts in hexane, even w/ crown ethers.  This man needs to increase the
density of hexane to 1.6, which would require molar levels of the
solute.