Most articles are saying that Skype federation is now available and "you're good to go with federation enabled".  The problem though is you are more than likely missing the "Skype" option when you select Add a contact not in my organization and you may need to enable PIC provisioning for Skype.  This guide will go through enabling PIC federation through Office 365 and bringing back the Skype icon to the Lync client.

NOTE: This guide assumes you have configured your edge servers and have verified federation to other partners works.

Here is what my Lync client looked like before following the instructions below:

Enabling Federation and Public IM Connectivity (PIC)

1. Login to your Office 365 Portal
2. Select Lync from the Admin dropdown
   
3. Select External Communications
4. Ensure the following settings:
   1. Domain federation mode: Turned on for all domains except blocked domains
   2. Public IM connectivity mode: Enabled
      
      

Adding Skype option to Lync Client

1. Navigate to your front end server
2. Open up the Lync 2010/2013 Management Shell
3. Execute the following command to list what providers you federate to
   1. Get-CsPublicProvider
4. If you have a provider that has a ProxyFqdn of federation.messenger.msn.com, execute the following command to remove it (replacing MSN with the Identity that had federation.messenger.msn.com for your environment):
   1. Remove-CsPublicProvider -Identity MSN
5. Execute the following command to add Skype as a federated provider
   1. New-CsPublicProvider -Identity Skype -ProxyFqdn federation.messenger.msn.com -IconUrl "https://images.edge.messenger.live.com/Messenger_16x16.png" -VerificationLevel 2 -Enabled 1
6. Close your Lync client and reopen for the option to be available

Adding Skype contacts to Lync

1. Click the Add a Contact icon
   
2. Select Add a Contact Not in My Organization
3. Select Skype.
   1. 
4. In the IM Address field, enter the Microsoft Account (MSA) of the Skype user in the format user(domain name)@msn.com.

   1. Example: If someone's email was [email protected], the entry would be bob(contoso.com)@msn.com

5. In the Add to contact group dropdown box, select the contact group to put the user in.
6. In the Set privacy relationship dropdown box, select the appropriate relationship.
7. Click OK.
8. NOTE: Once the Skype user adds your account, the federated user will appear online.  Until the user adds you to their Skype list, the contact will appear offline.

Adding Lync user to Skype

1. Sign into Skype
2. Click the Add User icon
   
3. Type in the user's SIP address
   1. For example: [email protected]
      1. Note: You do not need to use the MSA format when adding the contact to your list from Skype
4. Select (single click) the name when it appears in the search list
5. Click the Add to Contacts button
   
6. NOTE: If you add the user to Skype first before Lync, the user will show up with a question mark (?) icon for a status until the Lync user approves the request/adds you to their contacts list.

Awesome Tidbits

When setting up Lync-to-Skype federation for the first time, I was seeing the following symptom.  Lync users could see the Skype user Offline, the Skype user could not add the Lync user as it would not pull the directory, and IMs would not work because the users had not accepted each other.  Doing a log on the front end server, resulted with the following error message as well:

TL_INFO(TF_PROTOCOL) [0]1838.0B20::06/05/2013-14:36:41.206.00008d15 (SIPStack,SIPAdminLog::ProtocolRecord::Flush:2420.idx(196))[506561689] $$begin_record
Trace-Correlation-Id: 506561689
Instance-Id: B0B5F
Direction: incoming
Peer: myedgepool.mydomain.local:5061
Message-Type: response
SIP/2.0 480 temporary unavailable
Start-Line: SIP/2.0 480 temporary unavailable
FROM: "Jack Stromberg"<sip:[email protected]>;tag=0f6bccf745;epid=1aadaf98be
TO: <sip:person(hotmail.com)@msn.com>;tag=qwemztox
CALL-ID: a0b5bb30381640c08b30ee2bda403905
CSEQ: 1 INVITE
Via: SIP/2.0/TLS 192.168.169.221:53811;branch=z9hG4bK6DC1D74D.F39C6D8A52E04898;branched=FALSE;ms-received-port=53811;ms-received-cid=718100,SIP/2.0/TLS 192.168.170.142:50017;ms-received-port=50017;ms-received-cid=208A00
CONTENT-LENGTH: 0
ms-diagnostics: 1035;reason="Previous hop public IM provider did not report diagnostic information";Domain="msn.com";PeerServer="federation.messenger.msn.com";source="sip.mydomain.com"
ms-diagnostics-public: 1035;reason="Previous hop public IM provider did not report diagnostic information";Domain="msn.com";PeerServer="federation.messenger.msn.com"
$$end_record

Findings: Doing some research, the 480 temporary unavailable error with 1035;reason="Previous hop public IM provider did not report diagnostic information" means that there are federation issues.  Since I know I enabled PIC Federation through Office 365 and federation worked to other partners (hotmail users for example), I assumed this was an issue with the PIC configuration.

Solution: According to a technet article recently posted (http://community.office365.com/en-us/blogs/office_365_technical_blog/archive/2013/06/01/troubleshooting-lync-skype-connectivity.aspx) if you are having issues federating to Skype, you may have to toggle the Public IM Connectivity mode switch in your Office 365 Lync portal.  If you are a small business user, you are almost gaurenteed to be affected by the upgrade to Office 365 2013.  If you are an enterprise business, it appears you should be fine, but in my case, I still saw issues connecting under an underprise account.

Additionally, it turns out I needed to submit a request to the old PIC provisioning crew at Microsoft in another scenario.  Once they enabled federation to Skype, I was able to go on my merry way.  You can start the request process here (their website can be quite frustrating... I couldn't get half the pages to load and ended up sending them an email): https://pic.lync.com/provision/Logon/Logon.aspx?rret=https%3a%2f%2fpic.lync.com%2fprovision%2fAgreementNumber.aspx%2f