Unfortunately, PowerShell for O365 is not going to accomplish that. You can, however, use the CSOM to accomplish this. This link shows how to create a navigation node. Here is the main part of it:
string siteUrl = "http://server/sites/MySiteCollection";
ClientContext clientContext = new ClientContext(siteUrl);
Web site = clientContext.Web;
// Get the Quick Launch navigation node collection.
NavigationNodeCollection collQuickLaunchNode = site.Navigation.QuickLaunch;
// Set properties for a new navigation node.
NavigationNodeCreationInformation ciNavicationNode = new NavigationNodeCreationInformation();
ciNavicationNode.Title = "New Node";
ciNavicationNode.Url = "http://localhost";
// Create node as the last node in the collection.
ciNavicationNode.AsLastNode = true;
You can either execute this in console, or you can execute it in PowerShell, as shown in this link (you need the Microsoft.SharePoint.Client(.Runtime) dll's from the ISAPI folder in 15 hive).
Here is what it would look like in PowerShell:
$username = "username"
$password = "password"
$url = "https://site.sharepoint.com/sites/appdev"
$securePassword = ConvertTo-SecureString $password -AsPlainText -Force
Add-Type -Path (Join-Path ([System.Environment]::GetFolderPath("Desktop")) "15 Hive\ISAPI\Microsoft.SharePoint.Client.dll")
Add-Type -Path (Join-Path ([System.Environment]::GetFolderPath("Desktop")) "15 Hive\ISAPI\Microsoft.SharePoint.Client.Runtime.dll")
$clientCtx = New-Object Microsoft.SharePoint.Client.ClientContext($url)
$credentials = New-Object Microsoft.SharePoint.Client.SharePointOnlineCredentials($username,$securePassword)
$clientCtx.Credentials = $credentials
$web = $clientCtx.Web
$navColl = $web.Navigation.QuickLaunch
$newNavNode = New-Object Microsoft.SharePoint.Client.NavigationNodeCreationInformation
$newNavNode.Title = "Node Title"
$newNavNode.Url = "http://sharepoint.stackexchange.com"
$newNavNode.AsLastNode = $true
# I received an error after executing the above.
# I ignored it and moved on, and executed the following lines.
# The navigation node was added successfully, as shown in my screen cap.
I got an error at
$navColl.Add($newNavNode), but after the
$clientCtx.ExecuteQuery(), I checked my site, and the new navigation was there: