There are instructions on nuget.org on how to set up a package restore with TFS, including Visual Studio Online: http://docs.nuget.org/docs/reference/package-restore-with-team-build
It mentions that the default Build Process Templates for VSO already implements NuGet Package Restore workflow. So, supposedly, you need to do additional setup only when you customize the templates.
The proposed approach is to create a simple MSBuild project file that will be used to build the solution. You can include all the required targets there (e.g. Build, Rebuild, Clean) that will just invoke MSBuild on your solution file with specifying the corresponding target.
Additionally create a target for package restore - it will invoke NuGet.exe restore MySolution.sln
command. The common build targets will depend on this one.
<?xml version="1.0" encoding="utf-8"?>
<Project ToolsVersion="4.0"
DefaultTargets="Build"
xmlns="http://schemas.microsoft.com/developer/msbuild/2003">
<PropertyGroup>
<OutDir>$(MSBuildThisFileDirectory)bin</OutDir>
<Configuration>Release</Configuration>
<ProjectProperties>
OutDir=$(OutDir);
Configuration=$(Configuration);
</ProjectProperties>
</PropertyGroup>
<ItemGroup>
<Solution Include="$(MSBuildThisFileDirectory)src\*.sln" />
</ItemGroup>
<Target Name="RestorePackages">
<Exec Command=""$(MSBuildThisFileDirectory)tools\NuGet\NuGet.exe" restore "%(Solution.Identity)"" />
</Target>
<Target Name="Build" DependsOnTargets="RestorePackages">
<MSBuild Targets="Build"
Projects="@(Solution)"
Properties="$(ProjectProperties)" />
</Target>
<!-- other targets... -->
</Project>