You have several options to do this, each with their own advantages and disadvantages.
I always start looking whether the available session objects can be used. You'll find a great write-up of what the different session objects are in this SE topic.
The first, core/session, can be used but it isn't recommended. Data stored in this session persists as long as the cookies aren't cleared and will survive a log out / log in action, which is what we don't want since the data is customer-specific.
The customer/session is better suited but will be cleared when the user logs in during the checkout process (some 3rd party checkout extensions do this, I've noticed).
That leaves us with checkout/session. This one is great because even though it still persists between log in / log out, it'll be tied to a specific quote which is in turn tied to a specific customer. This session gets 'cleared' after successfully placing an order. Well, not really, since only the connection to the quote is removed so you'll be able to place another order. All the order data will still exist and thus be retrievable.
So I'd recommended setting the value in the checkout/session object in your observer or controller after retrieving the needed data and fetching it after placing the order. The event you should use for this is
This is always fired when an order is paid, which usually fires before showing the success screen.
There is one problem with this; if the payment for some reason fails and the customer later decides to pay the order using a link that was sent to them (many payment service providers do this), the data possibly isn't available any more. If this happens frequently, you should go with storing the data in the order object like you've described or even storing the data in the customer object when it's a logged in user.
When you add an attribute to the order entity, this isn't visible anywhere by default. You need to make it explicitly visible in the backend so if you don't do that, you should be fine.
This is an example of a setup script that you could place in your custom module to create an order attribute;
$installer = $this;
/* @var $installer Mage_Sales_Model_Mysql4_Setup */
$setup = new Mage_Eav_Model_Entity_Setup('core_setup');
$setup->addAttribute('order', 'your_data', array(
'position' => 1,
'type' => 'static',
'label' => 'Your Data',
'global' => 1,
'visible' => 0,
'required' => 0,
'user_defined' => 1,
'searchable' => 0,
'filterable' => 0,
'comparable' => 0,
'visible_on_front' => 0,
'visible_in_advanced_search' => 0,
'unique' => 0,
'is_configurable' => 0,
'text NOT NULL DEFAULT ""'
'text NOT NULL DEFAULT ""'
The code for adding it to a customer is similar, you should be able to work it out.