What OS are you using? I'm using Windows 7 Professional 64-bit with a Lexmark X4850 wireless all-in-one so the exact process may differ.
Try this first.
Please verify that your router is not set for WPA2 Personal (aka WPA2-PSK). The Deskjet 6840 is a great printer (I had one for years) but it does not support WPA2.
Next, let's try to manually configure the Deskjet 6840's network configuration via its internal web page.
Connect the Deskjet to the router via an Ethernet cable, get the IP address from the router or by printing the Deskjet's network configuration page (press the button with the check mark) and browse the printer's web page at that IP address.
On the printer's web page, select Network then Wireless. At this point you have two choices: use the Wireless Setup Wizard or go to the Advanced page and enter the SSID and WPA-PSK encryption key manually (don't forget to enable the radio and to set the mode to Infrastructure).
Now unplug the Ethernet cable from the printer and you should be on the network. You can check by printing the network configuration page and verify that it has a good IP address.
If that doesn't work, you can try this.
Step 1: Set the print processor
open Devices and Printers --> right-click the icon for your printer (Lexmark 4800 Series in my case)
click Printer Properties -- > Advanced tab --> Print Processor button
The default print processor is winprint and default data type is RAW. This does NOT work via wireless with the Lexmark (not sure about yours).
Besides winprint, you should see another proprietary print processor on the list, e.g. Lexmark, HP, Dell. Select the print processor from your printer manufacturer. Set the data type to RAW, and hit OK.
Step 2: Enable bidirectional support
After setting the print processor, click the Ports tab. Highlight the port for your printer and check Enable Bidirectional Support.