How to wire this linear Hall effect sensor
Have I wired something wrong?


Yes.
R1 is not required and will cause incorrect or no operation at values of much above 500 Ohms with a 9V supply.

The sensor operates with a "hard" supply on Vs, and will tolerate use of a 9V battery.
Adding a series resistor as you have done shows a misunderstanding of how the device works. 

As shown in the data sheet -  connect power supply to Vs+ and Vs-and take output from 'Output' and Vs-



The datasheet advise that Vs may be 4.5 to 10.5 volt.
Supply current is 7mA typical and 8.7 mA at Vs = 5 Vdc.
Operation from a 9V battery is acceptable. An Alkaline 9V battery will have an unloaded voltage when new of up to about 10 V absolute maximum, so is still within specification.

If you want a non varying Vs you should use a voltage regulator.
The series resistor will drop V = IR.
With a nominal 9V battery the 4.5V lower limit will be reached when R = V/I = 
(9-4.5)/ 0.0087A = 517 Ohms.
As the battery voltage falls an even smaller resistor would be required to allow correct operation. With resistors of " ... 1K, 10K, 100K, 1M" the devbice will not function.