If I cast Lignify on my opponent's Blightsteel Colossus and then deal 5 damage to it with one of my creatures, does it go to the graveyard since it has no abilities? Or is this ability regained once it is removed from the field since Lignify is destroyed at the same time?
The Colossus would be put into the graveyard because it doesn't have its "shuffle into its owner's library" ability when replacement effects would be checked.
At the moment that your Lignified Colossus dies, it's still a 0/4 with no abilities.
From the comp rules for replacement effects:
It regains its shuffle ability once it hits your graveyard (since Lignify is gone). But the time for checking replacement effects has already passed. It stays in your graveyard.