Turn on the 3D Graphics toolbar, adjust some of the default text graphics properties before you add a label so that it is added large enough to see/find.
Select the 3D Text tool
Use the 3D Text tool to click on the feature you want to label, and type in the label you wish to display. Adjust the label properties for orientation and size.
I've created a quick 3D layer to demonstrate the result:
This 3D Text will rotate with your scene as it does in the linked video. Unless the scene is using a third-party add-in for labels, I believe this is the only way to do it in ArcScene.