What are some examples of evolving networks in biology?
Others have nicely summarized to different types of biological networks and how they can evolve. I would like to make a fine distinction between evolution and dynamic adaptation and add some comments about relative evolvabilities of different biological networks. 

Given an architecture, a network can respond dynamically to different inputs. The preferred paths may change and the output characteristics can vary. Example cases include the effect of environment on metabolism. Personally, I would not consider this as network evolution because the architecture remains the same. Network evolution refers to rewiring or addition of new connections. 

It would be apt to classify the biological networks like this: 


molecular networks


Gene regulatory networks (GRN)
Molecular (protein-protein) interaction networks (PPI)
Cell signaling networks 

cellular networks


Neural networks
Biofilms (?)

organismal networks 


Ecological networks (food webs etc)



There are several ways in which a network can evolve: Edge addition, edge deletion, edge modification, node addition, node deletion and node duplication. 

In molecular networks edge modification happens when the chemical interaction is affected. For e.g. in a gene regulatory network a promoter-Transcription Factor (TF) interaction can change if there is a mutation in promoter sequence or in the DNA binding domain of TF. Similar situation exists in the cases of PPI and ligand-receptor interactions (Though concept of mutation doesn't apply to ligands). 
Gene (node) duplications are also common mechanism of evolution of GRN. Gene deletions/inactivations also change the network and in some cases result in complex diseases. Metabolic networks evolve if an enzyme mutates and a new pathway is created. 
Usually node additions rarely happen; node duplications and edge modifications are more common in molecular networks. 

In neural networks the plasticity is higher than molecular networks. There is a basic architecture that is essential to support life but the connections keep changing, nonetheless, in the non-core regions. Since active neurogenesis stops after a certain point, we can assume that number of nodes remains unchanged but edge addition (new synapse), edge deletion (synaptic pruning) and edge modification (long term potentiation/depression) is quite rampant and widespread. In neurodegenerative diseases neurons die and therefore nodes are lost.

Ecological networks are affected by environment and geological barriers. So there are several subnetworks (ecosystems) that are weakly or strongly connected with each other. Introduction of foreign species (node addition) causes immediate perturbation of the local network architecture. Long term effects arise because of extinction (node deletions), speciation (node evolution leading to edge modification i.e feeding habits etc).

It is also to be noted that in all the cases the effect of a change on a network depends on which node/edge is affected; hubs are under tight scrutiny and are protected from perturbations because any dysregulation can lead to network collapse. Some networks also follow the preferential attachment behavior (which appears contradictory to hub preservation as a mechanism). I guess that molecular networks do not employ preferential attachment whereas ecological networks do.