Hi Rob,
From Appearance > Widgets you should be able to add Search blocks as such: https://share.getcloudapp.com/7KuqZxzz
Alternatively, you can also add Search blocks/widgets through Block Elements.
See this for reference: https://share.getcloudapp.com/Wnuq8A6q
You just need to set the element type to “Right Sidebar” to make it appear in the sidebar. Take note that doing so through the Block Elements will remove the current sidebar widgets for the selected sidebar. Moreover, your layout must have a sidebar set for the Element to show.
Furthermore, if the Search widget/block is indeed missing, could you test for plugin conflict. Kindly check if any plugin is causing the widget to disappear. To do this, you would need to disable your plugins one by one.
Hope this helps! 🙂