Most probably, the taskbar is not lost, but rather is hidden. To get it back, try using Parallels Desktop's Applications menu->Show Windows Taskbar option.
If the task bar still doesn't appear, probably it is set to auto-hide mode. To get it back, try the following:
1. While in Windows, press the Command key on your Mac keyboard. This will have Windows start menu appear, as well as the taskbar.
2. Now, right-click the task bar and select "Properties" in the menu opened.
3. You see Taskbar and Start Menu Properties. Unselect the "Auto-hide the taskbar" option and hit "Apply" button.